Square packing explained

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

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 (in which case it is \sqrt{n} ), as well as for n = {} 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 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 =11 . It is known that 11 unit squares cannot be packed in a square of side length less than style 2+2 \sqrt{ 4 / 5 } ≈ 3 . 789 . By contrast, the tightest known packing of 11 squares is inside a square of side length approximately 3.877084 found by Walter Trump.^[1]

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 ≈ 4 . 6756 .

Asymptotic results

For larger values of the side length

a , the exact number of unit squares that can pack an a x a square remains unknown.It is always possible to pack a \lfloor a\rfloor x \lfloor a\rfloor grid of axis-aligned unit squares,but this may leave a large area, approximately 2 a(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} ) (here written in little o notation).Later, Graham and Fan Chung further reduced the wasted space to O(a ^{3/5} ) .However, as Klaus Roth and Bob Vaughan proved, all solutions must waste space at least \Omega l (a ^{1/2} (a - \lfloor a\rfloor) r ) . 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.

Some numbers of unit squares are never the optimal number in a packing. In particular,if a square of size

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

Square packing in a circle

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:

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

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

Notes and References

1. The 2000 version of listed this side length as 3.8772; the tighter bound stated here is from