Packing problems
Packing problems constitute a broad class of optimization challenges in mathematics and computer science, involving the arrangement of a set of objects—such as geometric shapes, bins, or abstract items—within a constrained space or container to achieve objectives like maximizing density, minimizing waste, or optimizing resource utilization, while ensuring no overlaps occur.[1] These problems are NP-hard in general, requiring heuristic or approximation algorithms for practical solutions, and they span discrete combinatorial settings to continuous geometric configurations.[2] Historically, packing problems trace back to early modern inquiries into efficient spatial arrangements, with the sphere-packing problem gaining prominence through Johannes Kepler's 1611 conjecture on the densest packing of equal spheres, later proven by Thomas Hales in 1998, achieving a maximum density of approximately 74% in three dimensions.[3] This conjecture, known as the Kepler problem, exemplifies geometric packing and has influenced fields from crystallography to materials science, where random packings like Bernal's model (density ~64%) simulate amorphous structures in liquids and solids.[3] Key variants include bin packing, which assigns items of varying sizes to fixed-capacity bins to minimize the number of bins used, with applications in logistics and scheduling; circle and sphere packing, focusing on non-overlapping placements in planes or spaces to maximize covered area or volume; and irregular packing, dealing with non-standard shapes in two or three dimensions for industrial cutting and nesting.[4][5][2] These problems arise in manufacturing sectors like shipbuilding, automotive production, and textile design, where optimizing material use reduces costs and waste, and in computational geometry for algorithm development using tools like semidefinite programming.[2][6]Introduction
Definition and scope
Packing problems are a class of optimization problems in mathematics that involve arranging a collection of objects within a given space, such as a bounded container or an unbounded region, without overlap between their interiors, to maximize the overall density or to fit as many objects as possible into the minimal space.[7][8] This arrangement requires that the objects remain disjoint in their interiors, though boundaries may contact, and allows for translational placements and, depending on the problem variant, rotational freedoms to achieve efficient configurations.[8][9] Unlike covering problems, which seek to fully occupy or envelop a space with possibly overlapping objects, or partitioning problems, which divide a space into disjoint subsets without regard to object shapes or densities, packing emphasizes non-overlapping placement to optimize resource use without complete space filling.[7][8] The scope of packing problems extends across various dimensions and object types, including one-dimensional intervals on a line, two-dimensional shapes in the plane, three-dimensional volumes, and higher-dimensional Euclidean spaces; it covers both regular geometric objects, such as equal circles or spheres, and irregular or heterogeneous forms, like polygons or polyhedra of differing sizes.[7][8] Settings can be continuous, as in geometric packings of the plane, or discrete, as in combinatorial bin packing with integer constraints, and may involve bounded containers of fixed capacity or unbounded spaces where the goal is asymptotic density maximization.[9][8] Representative examples illustrate this breadth: the problem of the densest packing of equal circles in the plane requires arranging infinitely many non-overlapping disks to cover the maximum proportion of area, while the bin packing problem entails fitting a finite set of unequal rectangles into the smallest number of fixed-size bins without overlap.[8][9] The efficiency of such arrangements is commonly assessed via packing density, which measures the proportion of space occupied by the objects.[8]Historical development
The study of packing problems has roots in classical geometry, with significant developments beginning in the Renaissance, culminating in Johannes Kepler's 1611 statement of the sphere packing problem: that no arrangement of equal spheres in three-dimensional space can exceed the density of the face-centered cubic or hexagonal close packing, achieving a density of \pi / (3\sqrt{2}).[10] Kepler's conjecture, inspired by observations of fruit and cannonball arrangements, marked a pivotal milestone, transforming intuitive geometric puzzles into rigorous mathematical challenges.[11] The 19th and early 20th centuries saw significant advances in two-dimensional packings, with Norwegian mathematician Axel Thue demonstrating in 1890 that the hexagonal lattice provides the optimal circle packing in the plane, though his initial proof was later refined in his 1910 publication to address gaps in rigor.[12] Building on this, Hungarian mathematician László Fejes Tóth extended Thue's results in the 1940s, proving in 1940 that lattice arrangements yield the densest packings for centrally symmetric convex sets in the plane and providing density bounds for general convex packings.[13] Concurrently, Hermann Minkowski's work in the geometry of numbers during the early 1900s introduced theorems on lattice packings, including the 1896 Minkowski theorem on convex bodies, which established fundamental bounds on the existence and density of lattice-based sphere packings in Euclidean space.[3] In the mid-20th century, C. A. Rogers advanced upper bound techniques for sphere packings in the 1950s, using simplex decompositions to derive estimates that improved upon earlier lattice-focused results and highlighted the challenges in non-lattice arrangements.[14] The Kepler conjecture endured as a central open problem until Thomas Hales announced a computer-assisted proof in 1998, involving exhaustive case analysis of tetrahedral decompositions, with the full details published in 2005 after rigorous verification.[15] Fejes Tóth's ongoing contributions in the 1950s, including strategies for sphere packing densities, influenced Hales' approach by emphasizing local density inequalities.[16] In 2001, Henry Cohn and Noam D. Elkies introduced linear programming bounds for sphere packing densities in low dimensions.[17] These methods contributed to later breakthroughs, including optimal packings in dimensions 8 and 24 by Maryna Viazovska (2016) and Henry Cohn, Abhinav Kumar, et al. (2017).[18][19] In 2025, Bo'az Klartag achieved a breakthrough by constructing lattice packings via stochastically evolving ellipsoids, yielding the most substantial improvement in high-dimensional sphere packing efficiency since Rogers' 1940s work and approaching the Minkowski-Hlawka asymptotic bound more closely.[20] These developments underscore the field's shift toward computational and probabilistic tools for tackling longstanding density limits.[21]Fundamentals of packing density
Measures of efficiency
In packing problems, the primary measure of efficiency is the packing density, denoted \delta, defined as the ratio of the total volume (or area in two dimensions) occupied by the packed objects to the volume (or area) of the containing space. This metric quantifies how effectively space is utilized, with higher values indicating better efficiency. For packings in unbounded infinite space, the packing density \delta is the supremum of the densities over all possible packings of the objects, often achieved through periodic or lattice arrangements and expressed as the asymptotic density—the limit superior of the filled proportion as the observation region expands to infinity.[22] In contrast, for finite containers, the exact packing density is computed directly as \delta = \frac{V_{\text{objects}}}{V_{\text{container}}}, where V_{\text{objects}} is the total volume of packed objects and V_{\text{container}} is the container volume; this can also be framed as the utilization ratio \delta = 1 - f_{\text{waste}}, with the waste fraction f_{\text{waste}} = \frac{V_{\text{container}} - V_{\text{objects}}}{V_{\text{container}}}.[23] Beyond density, other criteria evaluate packing efficiency depending on the context. In finite-space problems with a fixed container, maximizing the number of objects fitted serves as a direct efficiency measure, particularly when object sizes vary. For physical applications, such as cargo loading or granular materials, stability assesses whether the arrangement resists external forces like gravity or vibration without collapsing, often incorporating constraints from rigid body equilibrium. Additionally, in computational settings, the time required to generate a packing solution is a practical efficiency factor, balancing solution quality against resource constraints. For instance, in circle packings in the plane, density remains the central metric for comparing arrangements.[24]Known bounds and theorems
The Minkowski–Hlawka theorem establishes a foundational lower bound on the maximal density of lattice sphere packings in n-dimensional Euclidean space for n > 1. It asserts the existence of a lattice \Lambda such that the packing density \Delta satisfies \Delta \geq \frac{\zeta(n)}{2^{n}}, where \zeta(n) is the Riemann zeta function, which approaches 1 as n increases.[25] This existential result, relying on probabilistic arguments over the space of lattices, guarantees that lattice packings can achieve densities exponentially close to the trivial bound of 1 in high dimensions, though the lattices are not explicitly constructed.[26] In contrast, upper bounds limit the possible densities from above. C. A. Rogers provided the first non-trivial such bound in 1958 for arbitrary (not necessarily lattice) sphere packings in n dimensions, with the asymptotic form \Delta \lesssim (n/e) \cdot 2^{-n/2} as n \to \infty.[27] This bound, derived using integral geometry and estimates on the volumes of Voronoi cells, demonstrates that packing densities decay exponentially in high dimensions, though the rate is weaker than later improvements. For circle packings in the plane (n=2), László Fejes Tóth proved in 1940 that the hexagonal lattice achieves the optimal density among all packings of equal circles, with \Delta = \pi / \sqrt{12} \approx 0.9069. This theorem resolves the two-dimensional analog of the Kepler conjecture, confirming that no denser arrangement exists by combining area arguments with symmetrization techniques to show any optimal packing must be periodic and hexagonal.[28] A landmark improvement on upper bounds came from G. A. Kabatiansky and V. I. Levenshtein in 1978, who used spherical codes and zonal harmonics to derive \Delta \leq 2^{-0.599 n (1 + o(1))} for the maximal sphere packing density in n dimensions. This bound exhibits a sharper exponential decay than Rogers', establishing that densities drop at a rate of approximately $2^{-0.599 n} in high dimensions and remaining the strongest general upper bound for n \gtrsim [42](/page/42).[29] Recent advances have refined lower bounds using randomized constructions. In 2025, Boaz Klartag introduced a probabilistic method involving random perturbations of ellipsoids to improve Rogers' existential lower bound by a factor of \Omega(n) in n dimensions, yielding packings with center density \delta \gtrsim n^{2} \cdot 2^{-n}.[20] This approach iteratively adjusts ellipsoid axes via random growth until lattice constraints are met, on average expanding the volume beyond prior deterministic methods and highlighting the power of semi-random techniques in high-dimensional geometry.[21]Packings in unbounded space
Circle packings in the plane
Circle packings in the plane refer to arrangements of non-overlapping disks of specified radii in the infinite Euclidean plane \mathbb{R}^2. The disks are considered closed or open depending on whether tangency is allowed, but in standard formulations, interiors are disjoint while boundaries may touch. For circles of equal radius r, the condition for non-overlap requires that the Euclidean distance between any two centers is at least $2r. For packings of equal circles, the densest arrangement is achieved by the hexagonal lattice packing, in which the centers form a triangular lattice where each circle is tangent to six neighbors arranged at the vertices of a regular hexagon. This configuration yields a packing density of \delta = \frac{\pi}{\sqrt{12}} \approx 0.9069, defined as the proportion of the plane covered by the disks in the limit of large regions. Axel Thue first claimed this density as optimal in 1890, though his proof was incomplete; a rigorous proof was provided by László Fejes Tóth in 1940, confirming that no packing of equal circles exceeds this density.[30] For unequal circles, denser packings are possible by filling interstices with smaller disks, allowing the supremum density to approach 1 as the size distribution includes arbitrarily small radii. A canonical example is the Apollonian circle packing, constructed iteratively by inscribing circles tangent to three mutually tangent circles via Descartes' circle theorem, which relates the curvatures (reciprocals of radii) of four mutually tangent circles: if three circles have curvatures k_1, k_2, k_3, the fourth has curvature k_4 = k_1 + k_2 + k_3 \pm 2\sqrt{k_1 k_2 + k_1 k_3 + k_2 k_3}. Such packings exhibit fractal-like structure and achieve a radial density of $3/\pi \approx 0.9549, representing the asymptotic proportion of area covered as a function of distance from the origin.[31][32] Finite subsets of circle packings in the plane address arrangements of a fixed number n of disks maximizing local density or minimizing the enclosing radius while maintaining non-overlap. For equal circles, optimal configurations for small n (e.g., n \leq 19) are known and often form subsets of the hexagonal lattice, with densities approaching the infinite case as n grows. Insights from the Tammes problem—maximizing the minimum angular separation of n equal spherical caps on the unit sphere without overlap—can be projected to the plane via stereographic projection, which maps circles on the sphere to circles or lines in the plane while preserving tangency and non-intersection, yielding finite unequal circle packings suitable for local dense arrangements.[33]Sphere packings in three dimensions
Sphere packings in three dimensions involve arranging congruent, non-overlapping spheres in infinite Euclidean 3-space to maximize the proportion of space occupied, known as the packing density. The face-centered cubic (FCC) packing and hexagonal close packing (HCP) achieve the highest known density of \frac{\pi}{\sqrt{18}} \approx 0.7405, where each sphere contacts 12 neighbors in a highly symmetric lattice structure.[34] In the FCC arrangement, spheres are positioned at the corners and face centers of a cubic unit cell, while HCP stacks hexagonal layers in an ABAB pattern, both yielding identical global densities due to equivalent local coordination.[35] The Kepler conjecture, proposed in 1611, posits that no arrangement of equal spheres can surpass this density, a claim proven by Thomas Hales in 2005 through a combination of geometric analysis and exhaustive computer enumeration of possible configurations.[15] Hales' proof demonstrates that any packing exceeding \frac{\pi}{\sqrt{18}} leads to contradictions in tetrahedral or octahedral voids, confirming the FCC and HCP as optimal.[34] The proof further establishes that all optimal packings achieving this density are lattice-based, ruling out non-periodic or disordered arrangements at maximum efficiency; specifically, only FCC and HCP lattices attain it without defects.[34] This lattice exclusivity underscores the role of translational symmetry in 3D sphere packing optimality.Packings in higher dimensions
In higher dimensions, the sphere packing problem becomes increasingly challenging, with the maximal packing density decreasing exponentially as the dimension n increases. The best known upper bound on the density \Delta_n is due to Kabatiansky and Levenshtein, who established that \Delta_n \leq 2^{-0.599n + o(n)}.[36] This bound, derived using spherical codes and zonal functions, highlights the rapid sparsity of optimal packings in high dimensions, where most space remains unoccupied. Lattice packings, which arrange sphere centers on a regular grid, often provide the densest known configurations in specific dimensions, but their densities still fall below this asymptotic limit for large n. Notable achievements include the E_8 lattice in 8 dimensions, which achieves a density of \frac{\pi^4}{384} \approx 0.2537 and is proven optimal among all sphere packings by Maryna Viazovska in 2017.[18] Similarly, the Leech lattice in 24 dimensions yields a density of \frac{\pi^{12}}{12!} \approx 0.00193, also proven to be the unique optimal packing up to isometry by Cohn, Kumar, Miller, and Radchenko in 2017.[37] These "magic" dimensions stand out due to their exceptional symmetries, but beyond n=3, exact optima remain unknown except in these cases. In other dimensions, such as 4 through 7 or 9 through 23, the best lattice packings provide lower bounds, yet they do not match the Kabatiansky-Levenshtein upper bound. Random packings, generated by stochastic processes like greedy algorithms or sequential addition, offer practical constructions in high dimensions, achieving densities on the order of $2^{-n}. A 2024 breakthrough by Campos, Jenssen, Michelen, and Sahasrabudhe demonstrated that a random greedy method produces packings exceeding the 75-year-old Rogers lower bound, improving the constant factor asymptotically for arbitrary n.[38] Further advances in 2025 by Klartag introduced stochastically evolving ellipsoids to construct lattice packings with densities at least c n^2 2^{-n} for some universal constant c > 0, marking the first significant asymptotic improvement for lattices since the 1980s.[20] Numerical simulations have pushed these constructions to dimensions up to 22, revealing near-optimal densities in moderate high dimensions through computational optimization.[39] Despite these progresses, key open problems persist: the exact maximal density \Delta_n is unknown for all n > 3 except 8 and 24, and closing the gap between lower and upper bounds in general high dimensions remains unresolved. Recent 2024-2025 numerical efforts, leveraging advanced algorithms, have refined bounds in dimensions 10-20 but highlight the computational barriers to exact solutions.[20]Packings in one-dimensional containers
Interval packing on a line
Interval packing on a line addresses the fundamental one-dimensional case of the packing problem, involving the placement of non-overlapping intervals of specified lengths along a linear container, typically a line segment of unit length. This setup models scenarios such as scheduling tasks on a single processor or allocating storage in contiguous blocks, where the objective is to minimize unused space or the number of required segments. Unlike higher-dimensional variants, the one-dimensional nature allows for exact solutions in special cases but requires heuristics for general instances to achieve efficient packings. A key variant is the bin packing formulation, where intervals must be assigned to the minimum number of fixed-length bins (line segments) without overlap, assuming bin capacity normalized to 1 and interval lengths in (0,1]. In this context, packing density measures utilization as the ratio of total interval length to total bin length, with optimal packings approaching density 1 for large instances when intervals are suitably sized. When all intervals share identical lengths, the problem simplifies dramatically: they can be packed contiguously to fill bins exactly, yielding a trivial optimal density of 1 with no waste. The first-fit decreasing (FFD) heuristic provides an effective approximation for general cases. It begins by sorting the intervals in non-increasing order of length, then sequentially assigns each to the earliest bin with sufficient remaining space to accommodate it without overlap. This offline approach leverages the decreasing order to prioritize larger items, often resulting in more compact arrangements than online methods. Analysis shows that FFD guarantees a solution using at most \frac{11}{9} \OPT + 1 bins, where \OPT denotes the optimal number required, establishing its bounded performance relative to the optimum.Rod or bar packing variants
Rod or bar packing variants extend the basic one-dimensional interval packing by incorporating practical constraints such as fixed orientations, where items must be placed end-to-end along a line without rotation, as rotation is inherently infeasible in one dimension. In these variants, rods or bars may have variable lengths and specific sequencing requirements to minimize waste or adhere to manufacturing constraints, distinguishing them from unconstrained interval assignments.[40] The cutting stock problem is a foundational variant in this domain, focusing on minimizing waste when cutting required lengths of rods from fixed-length stock bars. In this setup, multiple stock bars of uniform length are trimmed to produce specified quantities of shorter pieces, with the objective of using the fewest stock bars possible to reduce material waste and production costs.[41] This problem arises commonly in industries like metalworking and paper manufacturing, where efficient cutting patterns directly impact resource utilization.[42] When rods have variable lengths—meaning the demanded cut pieces vary in size—the problem becomes NP-hard, as determining the minimum number of stock bars required is computationally intractable for large instances.[43] Approximation algorithms, particularly those based on linear programming relaxations, provide near-optimal solutions by generating cutting patterns through column generation techniques, where each column represents a feasible cutting pattern and the formulation minimizes the total stock used.[41] These methods balance computational efficiency with waste reduction. Recent advancements include deep reinforcement learning approaches, which achieve utilization rates over 90% on benchmark instances.[43]Packings in two-dimensional containers
Circles in squares or rectangles
The packing of circles into squares or rectangles seeks to arrange non-overlapping circles of equal or varying radii within a bounded rectangular container, typically to minimize the container dimensions for a fixed total circle area or to maximize packing density.Equal Circles in a Square
The problem of packing n equal circles into the smallest possible square is well-studied, with optimal solutions proven for small n and best-known configurations computed for larger n using numerical optimization techniques. Proven optima occur at n=1 (single circle, side length 2 for unit radius), n=4 (square lattice, side length 4, density π/4 ≈ 0.785), and n=9 (3×3 square lattice, side length 6, density π/4 ≈ 0.785), where the circles touch the boundaries and each other in a regular grid.[44] For other values, configurations often blend square and hexagonal arrangements, adjusted for boundary constraints, yielding densities below the infinite-plane hexagonal limit of π/(2√3) ≈ 0.9069 but improving asymptotically with n.[24] Best-known results up to n=100 have been obtained through iterative computational searches, such as branch-and-bound and stochastic optimization, with the minimal square side length s (for unit radius circles) increasing roughly as s ≈ 2√n for large n, though boundary inefficiencies persist.[44][45] For small n, the following table summarizes key metrics, where density δ = nπ / s2 and proven optima are marked:| n | Minimal side length s (unit radius) | Density δ | Proven optimal? |
|---|---|---|---|
| 1 | 2.0000 | 0.7854 | Yes |
| 2 | 3.4142 | 0.5390 | No |
| 3 | 3.9327 | 0.6096 | No |
| 4 | 4.0000 | 0.7854 | Yes |
| 5 | 4.8284 | 0.6738 | No |
| 6 | 5.3294 | 0.6640 | No |
| 7 | 5.7321 | 0.6693 | No |
| 8 | 5.8630 | 0.7310 | No |
| 9 | 6.0000 | 0.7854 | Yes |
| 10 | 6.7490 | 0.6900 | No |