Square packing

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.{{citation |last1=Brass |first1=Peter |last2=Moser |first2=William |last3=Pach |first3=János |author3-link=János Pach |year=2005 |title=Research Problems in Discrete Geometry |publisher=Springer |location=New York |isbn=978-0387-23815-9 |mr=2163782 |lccn=2005924022 |page=45 |url=https://books.google.com/books?id=WehCspo0Qa0C&pg=PA45}}

{{multiple image|total_width=540

|image1=5 kvadratoj en kvadrato.svg

|caption1=5 unit squares in a square of side length $2+1/\backslash sqrt\{2\}\backslash approx\; 2.707$

|image2=10 kvadratoj en kvadrato.svg

|caption2=10 unit squares in a square of side length $3+1/\backslash sqrt\{2\}\backslash approx\; 3.707$

|image3=Packing_11_unit_squares_in_a_square_with_side_length_3.87708359....svg

|caption3=11 unit squares in a square of side length

$a\backslash approx\; 3.877084$

}}

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 $\backslash 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 $\backslash lceil\backslash sqrt\{n\}\backslash ,\backslash rceil$, where $\backslash lceil\backslash ,\backslash \; \backslash rceil$ is the ceiling (round up) function.{{citation

| last = Bentz | first = Wolfram

| year = 2010

| title = Optimal packings of 13 and 46 unit squares in a square

| journal = The Electronic Journal of Combinatorics

| volume = 17

| number = R126

| doi = 10.37236/398

| mr = 2729375

| url = https://www.combinatorics.org/Volume_17/Abstracts/v17i1r126.html

| arxiv = 1606.03746

}}

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

| last = Friedman

| first = Erich

| year = 2009

| title = Packing unit squares in squares: a survey and new results

| journal = Electronic Journal of Combinatorics

| volume = 1000

| doi = 10.37236/28

| at = Dynamic Survey 7

| mr = 1668055

| url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS7

| doi-access = free

| access-date = 2018-02-23

| archive-date = 2018-02-24

| archive-url = https://web.archive.org/web/20180224053022/http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS7

| url-status = live

}}{{citation

| last = Stromquist

| first = Walter

| year = 2003

| title = Packing 10 or 11 unit squares in a square

| journal = Electronic Journal of Combinatorics

| volume = 10

| doi = 10.37236/1701

| mr = 2386538

| at = Research Paper 8

| url = http://www.combinatorics.org/Volume_10/Abstracts/v10i1r8.html

| access-date = 2011-06-01

| archive-date = 2011-06-04

| archive-url = https://web.archive.org/web/20110604002838/http://www.combinatorics.org/Volume_10/Abstracts/v10i1r8.html

| url-status = live

}}

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 $\backslash textstyle\; 2+2\backslash sqrt\{4/5\}\; \backslash approx\; 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.The 2000 version of {{harvtxt|Friedman|2009}} listed this side length as 3.8772; the tighter bound stated here is from {{citation

| last1 = Gensane | first1 = Thierry

| last2 = Ryckelynck | first2 = Philippe

| year = 2005

| title = Improved dense packings of congruent squares in a square

| journal = Discrete & Computational Geometry

| mr = 2140885

| doi = 10.1007/s00454-004-1129-z

| doi-access = free

| volume = 34

| issue = 1

| pages = 97–109

}}

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\backslash approx\; 4.6756$.

Below are the minimum solutions for values up to $n\; =\; 12$; the case $n=11$ remains unresolved:{{mathworld|id=SquarePacking |title=Square Packing }}

{{unsolved|mathematics|What is the asymptotic growth rate of wasted space for square packing in a half-integer square?}}

File:Mutilated chessboard vectorized.svg, the optimal packing for {{math|n² − 2}} squares]]

For larger values of the side length $a$, the exact number of unit squares that can pack an $a\backslash times\; a$ square remains unknown.

It is always possible to pack a $\backslash lfloor\; a\backslash rfloor\; \backslash !\backslash times\backslash !\; \backslash lfloor\; a\backslash rfloor$ grid of axis-aligned unit squares,

but this may leave a large area, approximately $2a(a-\backslash lfloor\; a\backslash 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).{{citation

| last1 = Erdős | first1 = P. | author1-link = Paul Erdős

| last2 = Graham | first2 = R. L. | author2-link = Ronald Graham

| year = 1975

| title = On packing squares with equal squares

| journal = Journal of Combinatorial Theory

| series = Series A

| doi = 10.1016/0097-3165(75)90099-0

| doi-access = free

| mr = 0370368

| volume = 19

| pages = 119–123

| url = http://www.math.ucsd.edu/~sbutler/ron/75_06_squares.pdf

}}

Later, Graham and Fan Chung further reduced the wasted space to $O(a^\{3/5\})$.{{citation

| last1 = Chung | first1 = Fan | author1-link = Fan Chung

| last2 = Graham | first2 = Ron | author2-link = Ronald Graham

| year = 2020

| title = Efficient packings of unit squares in a large square

| journal = Discrete & Computational Geometry

| doi = 10.1007/s00454-019-00088-9

| volume = 64

| issue = 3

| pages = 690–699

| url = https://www.math.ucsd.edu/~fan/wp/spacking.pdf

}}

However, as Klaus Roth and Bob Vaughan proved, all solutions must waste space at least $\backslash Omega\backslash bigl(a^\{1/2\}(a-\backslash lfloor\; a\backslash rfloor)\backslash bigr)$. In particular, when $a$ is a half-integer, the wasted space is at least proportional to its square root.{{citation

| last1 = Roth | first1 = K. F. | author1-link = Klaus Roth

| last2 = Vaughan | first2 = R. C. | author2-link = Bob Vaughan

| year = 1978

| title = Inefficiency in packing squares with unit squares

| journal = Journal of Combinatorial Theory

| series = Series A

| doi = 10.1016/0097-3165(78)90005-5

| doi-access = free

| mr = 0487806

| volume = 24

| issue = 2

| pages = 170–186

}} 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\backslash times\; a$ allows the packing of $n^2-2$ unit squares, then it must be the case that $a\backslash ge\; n$

and that a packing of $n^2$ unit squares is also possible.{{citation

| last1 = Kearney

| first1 = Michael J.

| last2 = Shiu

| first2 = Peter

| year = 2002

| title = Efficient packing of unit squares in a square

| journal = Electronic Journal of Combinatorics

| mr = 1912796

| volume = 9

| issue = 1

| doi = 10.37236/1631

| at = Research Paper 14, 14 pp.

| url = http://www.combinatorics.org/Volume_9/Abstracts/v9i1r14.html

| access-date = 2011-06-01

| archive-date = 2011-06-04

| archive-url = https://web.archive.org/web/20110604002820/http://www.combinatorics.org/Volume_9/Abstracts/v9i1r14.html

| url-status = live

}}

{{-}}

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 the minimum known solutions for up to $n\; =\; 12$ (although only the cases $n\; =\; 1$ and $n\; =\; 2$ are known to be optimal):{{citation |last=Friedman |first=Erich |date= |title=Squares in Circles |url=https://erich-friedman.github.io/packing/squincir/}}

Packing squares into other shapes can have high computational complexity: testing whether a given number of axis-parallel unit squares can fit into a given polygon is NP-complete. It remains NP-complete even for a simple polygon (with no holes) that is orthogonally convex, with axis-parallel sides, and with half-integer vertex coordinates.{{citation

| last1 = Abrahamsen | first1 = Mikkel

| last2 = Stade | first2 = Jack

| arxiv = 2404.09835

| contribution = Hardness of packing, covering and partitioning simple polygons with unit squares

| doi = 10.1109/FOCS61266.2024.00087

| pages = 1355–1371

| publisher = IEEE

| title = 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27–30, 2024

| year = 2024}}

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

{{reflist}}

• {{citation |title=Squares in Squares |series=Erich's Packing Center |last=Friedman |first=Erich |website=Github |url=https://kingbird.myphotos.cc/packing/squares_in_squares.html}}

{{Packing_problems}}

Category:Packing problems

Category:Unsolved problems in geometry