Packing polyominoes clumsily

DOI10.1016/J.COMGEO.2013.08.011MaRDI QIDQ390365zbMATH OpenOpenAlexFDO

Authors Stefan Walzer, Torsten Ueckerdt, Maria Axenovich

Publication date 8 January 2014

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2013.08.011

zbMATH Keywords

aperiodic clumsy density packing polyominoes sparse

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Polyominoes (05B50)

Review text

For a set \(D\) of polyominoes, a packing of the plane with \(D\) is a maximal set of copies of polyominoes from \(D\) that are non overlapping. \textit{A. Gyárfás} et al. [Discrete Math. 71, No. 1, 33--46 (1988; Zbl 0663.05021)] called a set of disjoint polyominoes a clumsy packing if no other polyomino can be added without an overlap and the total density is as small as possible.NEWLINENEWLINENEWLINE In this paper clumsy packing of general polyominoes are studied. The authors give an example of a set \(D\) of connected polyominoes such that every clumsy packing with \(D\) is aperiodic and compute the smallest possible density of a clumsy packing, denoted \(\mathrm {clum}(D)\), when \(D\) consists of a single polyomino of a given order \(k\) (\(\mathrm {clum}(D)\geq \frac{k}{k^2-k+1}\) and the inequality is tight). Also, it is shown that for any set \(D\) of polyominos (connected or not) and for any \(\epsilon >0\), there is a periodic packing \(P\) with \(D\) such that \(\mathrm {density}(P)-\mathrm {clum}(D)\leq \epsilon\) and the question whether, for a given set \(D\) of connected polyominoes and a given rational number \(d\), \(\mathrm {clum}(D) \leq d\), is undecidable.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Packing polyominoes clumsily

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390365)