Square packing
Two-dimensional packing problem
title: "Square packing" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["packing-problems", "unsolved-problems-in-geometry"] description: "Two-dimensional packing problem" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Square_packing" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Two-dimensional packing problem ::
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.
|image1=5 kvadratoj en kvadrato.svg |caption1=5 unit squares in a square of side length 2+1/\sqrt{2}\approx 2.707 |image2=10 kvadratoj en kvadrato.svg |caption2=10 unit squares in a square of side length 3+1/\sqrt{2}\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\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 \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.{{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 | 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 \textstyle 2+\frac{4}{\sqrt{5}} \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 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\approx 4.6756.
Below are the minimum solutions for values up to n = 12; the case n=11 remains unresolved: ::data[format=table]
| Number of unit squares n | Minimal side length a of big square |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 2 |
| 4 | 2 |
| 5 | 2.707... |
| 6 | 3 |
| 7 | 3 |
| 8 | 3 |
| 9 | 3 |
| 10 | 3.707... |
| 11 | 3.877... ? |
| 12 | 4 |
| :: |
Asymptotic results
::figure[src="https://upload.wikimedia.org/wikipedia/commons/4/47/Mutilated_chessboard_vectorized.svg" caption="''n''2 − 2}} squares"] ::
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}) (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 \Omega\bigl(a^{1/2}(a-\lfloor a\rfloor)\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
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.{{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
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 the minimum known solutions for up to n = 12 (although only the cases n = 1 and n = 2 are known to be optimal):
::data[format=table]
| Number of squares | Circle radius |
|---|---|
| 1 | \sqrt{2}/2 \approx 0.707\ldots |
| 2 | |
| 3 | 5\sqrt{17}/16 \approx 1.288\ldots |
| 4 | \sqrt{2} \approx 1.414\ldots |
| 5 | \sqrt{10}/2 \approx 1.581\ldots |
| 6 | 1.688... |
| 7 | \sqrt{13}/2 \approx 1.802\ldots |
| 8 | 1.978... |
| 9 | \sqrt{1105}/16 \approx 2.077\ldots |
| 10 | 3\sqrt{2}/2 \approx 2.121\ldots |
| 11 | 2.214... |
| 12 | \sqrt{5} \approx 2.236\ldots |
| :: |
In other shapes
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}}
References
References
- (2005). "Research Problems in Discrete Geometry". Springer.
- "Square Packing".
- Friedman, Erich. "Squares in Circles".
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::