Packing polyominoes clumsily (Q390365): Difference between revisions

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. 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.