×

Efficient packing of unit squares in a square. (English) Zbl 0993.05044

Electron. J. Comb. 9, No. 1, Research paper R14, 14 p. (2002); printed version J. Comb. 9, No. 1 (2002).
Let \(s(N)\) denote the edge length of the smallest square in which one can pack \(N\) unit squares. The function \(s(N)\) is increasing and satisfies \(s(n^2)= n\), so that \(\sqrt N\leq s(N)\leq \lceil\sqrt N\rceil\). The authors prove that \(s(6)= s(7)= 3\). Moreover, they investigate the case \(N= n^2+1\). Define \(\delta_n:= s(n^2+ 1)-n\). Then \(\delta_{n+1}\leq \delta_n\), and it is proved that \(\delta_n\leq {3\over (2n)^{1/3}}+ {3\over (2n)^{2/3}}\) for all \(n\geq 1\). For \(r> 1\), let \(n_r\) be the smallest integer \(n\) such that \(\delta_n\leq 1/r\). The authors use an explicit construction to show that \(n_r\leq {27\over 2} r^3+ O(r^2)\), and also that \(n_2\leq 43\).

MSC:

05B40 Combinatorial aspects of packing and covering
52C15 Packing and covering in \(2\) dimensions (aspects of discrete geometry)
PDFBibTeX XMLCite
Full Text: EuDML EMIS