Square packing
Square packing is a classic problem in discrete geometry and packing theory, concerned with the arrangement of non-overlapping squares—either of equal or varying sizes—into a bounded region such as a larger square, rectangle, or infinite strip, with the goal of minimizing the container's dimensions, maximizing the number of squares fitted, or achieving the highest possible density without gaps or overlaps beyond boundaries.[1][2] A central variant, known as square packing in a square, focuses on determining the smallest side length of a containing square that can hold n unit squares (side length 1), typically axis-aligned without rotations, though configurations allowing arbitrary orientations are also studied.[1][3] For perfect packings where n = k2 for integer k, the minimal side length is exactly k, but for other n, suboptimal arrangements leave gaps, and the optimal side length s(n) satisfies √n ≤ s(n) ≤ √n + 1.[3] Optimal solutions have been rigorously proven for small n such as 2, 3, 5–8, 10, 13, 14, 15, 24, 34, 35, 46–48, with more values proven in recent years; known packings and bounds are available up to n=324 as of 2025, often involving intricate tilted layouts.[1][3][4] Other notable variants include packing unequal squares into a unit square bin (relevant to bin packing algorithms), online square packing where squares arrive sequentially without foreknowledge of sizes, and multidimensional extensions like cube packing in 3D.[5][6] These problems, dating back to the 1970s with the problem formally posed by Erdős and Graham in 1975, are NP-hard in general, connecting to applications in materials science, VLSI chip design, and resource allocation.[7][8]Fundamentals
Definitions and Objectives
Square packing refers to the arrangement of non-overlapping squares—either of equal or varying sizes (with equal-sized squares often taken as unit squares for convenience)—without overlap or protrusion into a larger container shape, such as a square, circle, or other polygon, with the aim of either maximizing the number of squares accommodated or minimizing the container's size for a given number of squares.[1] This geometric optimization problem emphasizes efficient space utilization while adhering to non-overlapping constraints, where interiors of the squares remain disjoint and fully contained within the boundary of the host shape.[3] The core objectives are typically framed in dual ways: for a fixed integer n, determine the smallest side length s(n) of a square that can enclose n unit squares; alternatively, for a container of fixed dimensions, identify the maximum n that can be packed inside it.[9] Packings may be restricted to axis-aligned orientations, with all squares parallel to the container's axes for simplicity, or permit rotations, allowing arbitrary angles that frequently yield denser configurations by better filling interstitial spaces.[3] Historically, square packing emerged in early 20th-century recreational mathematics, gaining formal rigor through problems posed by Paul Erdős in the 1930s for Hungarian high school students and subsequent analysis by Erdős and Ronald L. Graham in the 1970s.[10] In asymptotic settings for large containers, packings achieve densities approaching 1, though quantifying the minimal wasted space remains a key challenge.[9]Types of Packings
Square packing problems can be categorized based on the sizes of the squares, their orientations, and additional constraints imposed on the arrangement. The most fundamental variant involves packing equal-sized squares, where all squares are identical unit squares, and the goal is to arrange them without overlaps or gaps within a container to maximize density or minimize the container size. This type forms the primary focus of research in square packing, as it simplifies analysis while capturing core geometric challenges. In contrast, unequal square packing allows squares of varying sizes, often aiming for a perfect dissection or tiling of a larger square without any wasted space. A notable example is the squared square, which is a square tiled by smaller squares of different sizes, all distinct. The first simple perfect squared square, using 21 unequal squares, was constructed by A. J. W. Duijvestijn in 1978, marking a milestone in the field after decades of manual and computational efforts.[11] Another key distinction lies in the orientation of the squares: axis-aligned packings require all squares to have sides parallel to the container's boundaries, promoting simplicity in computation and implementation. Rotated packings, however, permit squares to be oriented at arbitrary angles, such as 45 degrees, which can achieve higher densities in certain non-rectangular containers by allowing more flexible nesting. Common constraints across these variants include prohibitions on overlaps between squares and requirements that no square protrudes beyond the container's boundaries, ensuring a valid enclosure. Specialized subproblems introduce further restrictions, such as online packing, where squares arrive sequentially and must be placed irrevocably without knowledge of future items, or packings tolerant of defects like small gaps for practical manufacturing. These variants find brief applications in areas like bin packing algorithms and VLSI circuit design, where efficient space utilization is critical.Packing into a Square
Finite Configurations
The function s(n) denotes the side length of the smallest square that can contain n non-overlapping unit squares, allowing rotations but no overlaps or extensions beyond the boundary.[12] For perfect square numbers n = k^2, the optimal packing is a k \times k grid arrangement with s(n) = k, achieving zero wasted space.[3] This trivial configuration extends to nearby values, such as n = k^2 - 1, by removing one square from the grid, though more efficient rotated placements often reduce s(n) for non-square n.[9] Exact or proven optimal values of s(n) are known for small n, with constructions relying on axis-aligned grids for many cases and rotated squares for others to minimize the enclosing side. For instance, the optimal packing of 5 unit squares uses a configuration where four squares form a 2x2 block and the fifth is rotated 45 degrees and placed in the corner, yielding s(5) = 2 + \frac{1}{\sqrt{2}} \approx 2.707, proven optimal by a simple area and positioning argument.[3] Similarly, for 10 squares, a symmetric extension incorporates additional rotated squares, achieving s(10) = 3 + \frac{1}{\sqrt{2}} \approx 3.707, also proven optimal.[12] The following table summarizes known optimal or best-known values of s(n) for selected small n, where exact values are integers for grid-based packings and approximations indicate upper bounds from constructions (lower bounds match in proven cases):| n | s(n) | Notes |
|---|---|---|
| 1 | 1 | Trivial single square. |
| 2–4 | 2 | 2x2 grid (optimal). |
| 5 | $2 + \frac{1}{\sqrt{2}} \approx 2.707 | Rotated placement (proven). |
| 6–9 | 3 | Near-grid (optimal for 6–9). |
| 10 | $3 + \frac{1}{\sqrt{2}} \approx 3.707 | Rotated extension (proven). |
| 13–15 | 4 | Near 4x4 grid (optimal for 14–15). |
| 24 | 5 | Proven optimal construction. |
| 34–35 | 6 | Near 6x6 grid (optimal for 35). |
| 46–48 | 7 | Near 7x7 grid. |
Asymptotic Bounds
The asymptotic density of packings of unit squares into a large square of side length s approaches 1 as s \to \infty, meaning the wasted area W(s) = s^2 - \max\{n : s(n) \leq s\} satisfies W(s) = o(s^2), where s(n) denotes the side length of the smallest square that can contain n unit squares. However, more precise bounds reveal that W(s) grows sublinearly but non-trivially. A seminal upper bound of W(s) = O(s^{7/11}) was established by Erdős and Graham through explicit constructions.[12] This was improved by Chung and Graham to W(s) = O(s^{3/5}) using a recursive partitioning strategy that divides the large square into regions packed with aligned and rotated squares.[14] On the lower bound, Roth and Vaughan proved that W(s) = \Omega(\sqrt{s} \cdot (s - \lfloor s \rfloor)) under certain conditions on the fractional part, implying in particular that W(s) \neq o(\sqrt{s}) and establishing a non-trivial inefficiency for infinitely many s.[15] This result shows that the wasted area cannot be bounded by any function growing slower than \sqrt{s}. Post-2000 developments, including the 2009 refinement by Chung and Graham, have narrowed the gap between upper and lower bounds, but the optimal exponent remains open, with a conjecture that W(s) = O(\sqrt{s}).[12] For side lengths s that are half-integers (i.e., s = k + 1/2 for integer k), the minimal wasted space is conjectured to grow more slowly than the general case, potentially bounded by a constant or logarithmic term, though the precise growth rate is an unresolved open problem.[12] This conjecture arises because half-integer sides allow for more symmetric dissections, potentially minimizing gaps near the boundaries. Regarding the asymptotic form of s(n), it is known that \sqrt{n} \leq s(n) \leq \sqrt{n} + 1, but finer expansions are of interest. The Roth-Vaughan lower bound implies s(n) = \sqrt{n} + \Omega(n^{1/4}) for infinitely many n, reflecting periodic fluctuations due to the fractional part of \sqrt{n}. A heuristic suggests s(n) \sim \sqrt{n} + \Theta(n^{1/4}), capturing the scale of these oscillations, though the upper bound matching this order remains unproven, with only weaker envelopes like O(n^{1/3}) or better from constructions available in the literature.[3]Packing into a Circle
Known Packings for Small n
The known packings of unit squares into the smallest enclosing circle for small values of n have been determined through computational searches, with only a few cases rigorously proven optimal. These results provide exact or near-exact minimal radii r(n), where the squares may be rotated and translated but not overlapped. The configurations often exploit symmetry for smaller n, transitioning to more complex arrangements as n increases.[16] The following table summarizes the minimal known radii r(n) for n = 1 to $12, including exact expressions where available and numerical approximations. Only the cases for n=1 and n=2 are proven optimal, while n=3 was rigorously verified as optimal in 2018 using computer-assisted optimization. Higher values represent best-known packings from exhaustive searches.[16][17]| n | Exact r(n) | Approximation |
|---|---|---|
| 1 | \sqrt{2}/2 | 0.707 |
| 2 | \sqrt{5}/2 | 1.118 |
| 3 | $5\sqrt{17}/16 | 1.288 |
| 4 | \sqrt{2} | 1.414 |
| 5 | \sqrt{10}/2 | 1.581 |
| 6 | \sqrt{(19706163 + 13275064\sqrt{2} - 40\sqrt{(443374242065 + 313512226176\sqrt{2})})/534} | 1.688 |
| 7 | \sqrt{13}/2 | 1.803 |
| 8 | - | 1.978 |
| 9 | \sqrt{1105}/16 | 2.077 |
| 10 | $3\sqrt{2}/2 | 2.121 |
| 11 | - | 2.214 |
| 12 | \sqrt{5} | 2.236 |