Square packing

Square packing is a packing problem where the objective is to determine how many congruent squares can be packed into some larger shape, often a square or circle.

Square packing is a packing problem where the objective is to determine how many congruent squares can be packed into some larger shape, often a square or circle.

In a square

Square packing in a square is the problem of determining the maximum number of unit squares (squares of side length one) that can be packed inside a larger square of side length a . If a is an integer, the answer is a^2, but the precise – or even asymptotic – amount of unfilled space for an arbitrary non-integer a is an open question. The smallest value of a that allows the packing of n unit squares is known when n is a perfect square, one less than a perfect square, or two less than a perfect square, as well as for n equal to 5, 6, 10, 13, and 46. For all of these numbers except 5 and 10, the packing is the natural one with axis-aligned squares, and the optimal value of a is \lceil\sqrt{n}\,\rceil , where \lceil\,\ \rceil is the ceiling (round up) function. The figure shows the optimal packings for 5 and 10 squares, the two smallest numbers of squares for which the optimal packing involves tilted squares. The smallest unresolved case is n=12 . It is known that 12 unit squares cannot be packed in a square of side length less than \textstyle \frac{7943}{2000} = 3.9715 . By contrast, the tightest known packing of 12 squares is inside a square of side length 4, in three rows of four. The optimal packing for n=11 was shown on September 29, 2026 in an AI-assisted proof to be approximately 3.877084, using Walter Trump's original packing from 1979. The smallest case where the best known packing involves squares at three different angles is n=17 . It was discovered in 1998 by John Bidwell, an undergraduate student at the University of Hawaiʻi, and has side length a\approx 4.6756 . , an optimal packing for squares Below are the minimum solutions for values up to n = 16 ; the case n=12 remains unresolved. Some numbers of unit squares are never the optimal number in a packing. In particular, if a square of size a\times a allows the packing of n^2-2 unit squares, then it must be the case that a\ge n and that a packing of n^2 unit squares is also possible.

Asymptotic results

For larger values of the side length a , the exact number of unit squares that can pack an a\times a square remains unknown. It is always possible to pack a \lfloor a\rfloor \!\times\! \lfloor a\rfloor grid of axis-aligned unit squares, but this may leave a large area, approximately 2a(a-\lfloor a\rfloor) , uncovered and wasted. Instead, Paul Erdős and Ronald Graham showed that for a different packing by tilted unit squares, the wasted space could be significantly reduced to O(a^{7/11}) \subseteq o(a^{0.637}) (the latter written in little o notation). Later, Graham and Fan Chung further reduced the wasted space to O(a^{0.631}) , and subsequent work reduced the wasted space to O(a^{0.625}) , and then O(a^{0.6}) . However, as Klaus Roth and Bob Vaughan proved, all solutions must waste space at least \Omega\bigl((a \cdot |a-\operatorname{round} a|)^{1/2}\bigr) . In particular, when a is a half-integer, the wasted space is at least proportional to its square root. The precise asymptotic growth rate of the wasted space, even for half-integer side lengths, remains an open problem. Square packing in a circle is a related problem of packing n unit squares into a circle with radius as small as possible. For this problem, good solutions are published for n up to 50. Here are the minimum known solutions for up to n = 12 (although only the cases from n = 1 to 7 are proven to be optimal):

See also

Circle packing in a square Squaring the square Rectangle packing Moving sofa problem

References

External links

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378993193 under CC BY-SA 4.0; modifications have been made.