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 in a square
[edit]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 . If is an integer, the answer is but the precise – or even asymptotic – amount of unfilled space for an arbitrary non-integer is an open question.[1]
The smallest value of that allows the packing of unit squares is known when is a perfect square (in which case it is ), as well as for 2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47, and 48. For most of these numbers (with the exceptions only of 5 and 10), the packing is the natural one with axis-aligned squares, and is , where is the ceiling (round up) function.[2][3] 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.[4][5]
The smallest unresolved case is . It is known that 11 unit squares cannot be packed in a square of side length less than . By contrast, the tightest known packing of 11 squares is inside a square of side length approximately 3.8771. It was found in 1979 by Walter Trump.[4]
The smallest case where the best known packing involves squares at three different angles is . It was discovered in 1998 by John Bidwell, an undergraduate student at the University of Hawaiʻi, and has side length .[4]
Asymptotic results
[edit]For larger values of the side length , the exact number of unit squares that can pack an square remains unknown. It is always possible to pack a grid of axis-aligned unit squares, but this may leave a large area, approximately , uncovered and wasted.[4] 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 (here written in little o notation).[6] Later, Graham and Fan Chung further reduced the wasted space to .[7] However, as Klaus Roth and Bob Vaughan proved, all solutions must waste space at least . In particular, when is a half-integer, the wasted space is at least proportional to its square root.[8] The precise asymptotic growth rate of the wasted space, even for half-integer side lengths, remains an open problem.[1]
Some numbers of unit squares are never the optimal number in a packing. In particular, if a square of size allows the packing of unit squares, then it must be the case that and that a packing of unit squares is also possible.[2]
Square packing in a circle
[edit]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 known for n up to 35. Here are minimum solutions for n up to 12:[9]
Number of squares | Circle radius |
---|---|
1 | 0.707... |
2 | 1.118... |
3 | 1.288... |
4 | 1.414... |
5 | 1.581... |
6 | 1.688... |
7 | 1.802... |
8 | 1.978... |
9 | 2.077... |
10 | 2.121... |
11 | 2.214... |
12 | 2.236... |
See also
[edit]References
[edit]- ^ a b Brass, Peter; Moser, William; Pach, János (2005), Research Problems in Discrete Geometry, New York: Springer, p. 45, ISBN 978-0387-23815-9, LCCN 2005924022, MR 2163782
- ^ a b Kearney, Michael J.; Shiu, Peter (2002), "Efficient packing of unit squares in a square", Electronic Journal of Combinatorics, 9 (1), Research Paper 14, 14 pp., doi:10.37236/1631, MR 1912796
- ^ Bentz, Wolfram (2010), "Optimal packings of 13 and 46 unit squares in a square", The Electronic Journal of Combinatorics, 17 (R126), arXiv:1606.03746, doi:10.37236/398, MR 2729375
- ^ a b c d Friedman, Erich (2009), "Packing unit squares in squares: a survey and new results", Electronic Journal of Combinatorics, Dynamic Survey 7, doi:10.37236/28, MR 1668055
- ^ Stromquist, Walter (2003), "Packing 10 or 11 unit squares in a square", Electronic Journal of Combinatorics, 10, Research Paper 8, doi:10.37236/1701, MR 2386538
- ^ Erdős, P.; Graham, R. L. (1975), "On packing squares with equal squares" (PDF), Journal of Combinatorial Theory, Series A, 19: 119–123, doi:10.1016/0097-3165(75)90099-0, MR 0370368
- ^ Chung, Fan; Graham, Ron (2020), "Efficient packings of unit squares in a large square" (PDF), Discrete & Computational Geometry, 64 (3): 690–699, doi:10.1007/s00454-019-00088-9
- ^ Roth, K. F.; Vaughan, R. C. (1978), "Inefficiency in packing squares with unit squares", Journal of Combinatorial Theory, Series A, 24 (2): 170–186, doi:10.1016/0097-3165(78)90005-5, MR 0487806
- ^ Friedman, Erich, Squares in Circles
External links
[edit]- Friedman, Erich, "Squares in Squares", Github, Erich's Packing Center