Respect all members: no insults, harassment, or hate speech.
Be tolerant of different viewpoints, cultures, and beliefs. If you do not agree with others, just create separate note, article or collection.
Clearly distinguish between personal opinion and fact.
Verify facts before posting, especially when writing about history, science, or statistics.
Promotional content must be published on the “Related Services and Products” page—no more than one paragraph per service. You can also create subpages under the “Related Services and Products” page and publish longer promotional text there.
Do not post materials that infringe on copyright without permission.
Always credit sources when sharing information, quotes, or media.
Be respectful of the work of others when making changes.
Discuss major edits instead of removing others' contributions without reason.
If you notice rule-breaking, notify community about it in talks.
Do not share personal data of others without their consent.
Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.
A container, usually a two- or three-dimensional convex region, possibly of infinite size. Multiple containers may be given depending on the problem.
A set of objects, some or all of which must be packed into one or more containers. The set may contain different objects with their sizes specified, or a single object of a fixed dimension that can be used repeatedly.
Usually the packing must be without overlaps between goods and other goods or the container walls. In some variants, the aim is to find the configuration that packs a single container with the maximal packing density. More commonly, the aim is to pack all the objects into as few containers as possible.[1] In some variants the overlapping (of objects with each other and/or with the boundary of the container) is allowed but should be minimized.
Many of these problems, when the container size is increased in all directions, become equivalent to the problem of packing objects as densely as possible in infinite Euclidean space. This problem is relevant to a number of scientific disciplines, and has received significant attention. The Kepler conjecture postulated an optimal solution for packing spheres hundreds of years before it was proven correct by Thomas Callister Hales. Many other shapes have received attention, including ellipsoids,[2]Platonic and Archimedean solids[3] including tetrahedra,[4][5]tripods (unions of cubes along three positive axis-parallel rays),[6] and unequal-sphere dimers.[7]
The hexagonal packing of circles on a 2-dimensional Euclidean plane.
These problems are mathematically distinct from the ideas in the circle packing theorem. The related circle packing problem deals with packing circles, possibly of different sizes, on a surface, for instance the plane or a sphere.
The counterparts of a circle in other dimensions can never be packed with complete efficiency in dimensions larger than one (in a one-dimensional universe, the circle analogue is just two points). That is, there will always be unused space if people are only packing circles. The most efficient way of packing circles, hexagonal packing, produces approximately 91% efficiency.[8]
In three dimensions, close-packed structures offer the best lattice packing of spheres, and is believed to be the optimal of all packings. With 'simple' sphere packings in three dimensions ('simple' being carefully defined) there are nine possible definable packings.[9] The 8-dimensional E8 lattice and 24-dimensional Leech lattice have also been proven to be optimal in their respective real dimensional space.
Cubes can easily be arranged to fill three-dimensional space completely, the most natural packing being the cubic honeycomb. No other Platonic solid can tile space on its own, but some preliminary results are known. Tetrahedra can achieve a packing of at least 85%. One of the best packings of regular dodecahedra is based on the aforementioned face-centered cubic (FCC) lattice.
Simulations combining local improvement methods with random packings suggest that the lattice packings for icosahedra, dodecahedra, and octahedra are optimal in the broader class of all packings.[3]
Determine the minimum number of cuboid containers (bins) that are required to pack a given set of item cuboids. The rectangular cuboids to be packed can be rotated by 90 degrees on each axis.
The problem of finding the smallest ball such that kdisjoint open unit balls may be packed inside it has a simple and complete answer in n-dimensional Euclidean space if , and in an infinite-dimensional Hilbert space with no restrictions. It is worth describing in detail here, to give a flavor of the general problem. In this case, a configuration of k pairwise tangent unit balls is available. People place the centers at the vertices of a regular dimensional simplex with edge 2; this is easily realized starting from an orthonormal basis. A small computation shows that the distance of each vertex from the barycenter is . Moreover, any other point of the space necessarily has a larger distance from at least one of the k vertices. In terms of inclusions of balls, the k open unit balls centered at are included in a ball of radius , which is minimal for this configuration.
To show that this configuration is optimal, let be the centers of k disjoint open unit balls contained in a ball of radius r centered at a point . Consider the map from the finite set into taking in the corresponding for each . Since for all , this map is 1-Lipschitz and by the Kirszbraun theorem it extends to a 1-Lipschitz map that is globally defined; in particular, there exists a point such that for all one has , so that also . This shows that there are k disjoint unit open balls in a ball of radius rif and only if. Notice that in an infinite-dimensional Hilbert space this implies that there are infinitely many disjoint open unit balls inside a ball of radius r if and only if . For instance, the unit balls centered at , where is an orthonormal basis, are disjoint and included in a ball of radius centered at the origin. Moreover, for , the maximum number of disjoint open unit balls inside a ball of radius r is
People determine the minimum height h of a cylinder with given radius R that will pack n identical spheres of radius r (< R).[12] For a small radius R the spheres arrange to ordered structures, called columnar structures.
People are given nunit circles, and have to pack them in the smallest possible container. Several kinds of containers have been studied:
Packing circles in a circle - closely related to spreading points in a unit circle with the objective of finding the greatest minimal separation, dn, between points. Optimal solutions have been proven for n ≤ 14, and n = 19.
Packing circles in a square - closely related to spreading points in a unit square with the objective of finding the greatest minimal separation, dn, between points. To convert between these two formulations of the problem, the square side for unit circles will be . The optimal packing of 15 circles in a squareOptimal solutions have been proven for n ≤ 30.
People are given nunit squares and have to pack them into the smallest possible container, where the container type varies:
Packing squares in a square: Optimal solutions have been proven for n from 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100, and any squareinteger. The wasted space is asymptotically O(a3/5).
Packing squares in a circle: Good solutions are known for n ≤ 35.The optimal packing of 10 squares in a square
Packing identical rectangles in a rectangle: The problem of packing multiple instances of a single rectangle of size (l,w), allowing for 90° rotation, in a bigger rectangle of size (L,W ) has some applications such as loading of boxes on pallets and, specifically, woodpulp stowage. For example, it is possible to pack 147 rectangles of size (137,95) in a rectangle of size (1600,1230).
Packing different rectangles in a rectangle: The problem of packing multiple rectangles of varying widths and heights in an enclosing rectangle of minimum area (but with no boundaries on the enclosing rectangle's width or height) has an important application in combining images into a single larger image. A web page that loads a single larger image often renders faster in the browser than the same page loading multiple small images, due to the overhead involved in requesting each image from the web server. The problem is NP-complete in general, but there are fast algorithms for solving small instances.
In tiling or tessellation problems, there are to be no gaps, nor overlaps. Many of the puzzles of this type involve packing rectangles or polyominoes into a larger rectangle or other square-like shape.
There are significant theorems on tiling rectangles (and cuboids) in rectangles (cuboids) with no gaps or overlaps:
An a × b rectangle can be packed with 1 × n strips if and only if n divides a or n divides b.[15][16]
The study of polyomino tilings largely concerns two classes of problems: to tile a rectangle with congruent tiles, and to pack one of each n-omino into a rectangle.
A classic puzzle of the second kind is to arrange all twelve pentominoes into rectangles sized 3×20, 4×15, 5×12 or 6×10.
Packing of irregular objects is a problem not lending itself well to closed form solutions; however, the applicability to practical environmental science is quite important. For example, irregularly shaped soil particles pack differently as the sizes and shapes vary, leading to important outcomes for plant species to adapt root formations and to allow water movement in the soil.[17]
^Minkowski, H. Dichteste gitterförmige Lagerung kongruenter Körper. Nachr. Akad. Wiss. Göttingen Math. Phys. KI. II 311–355 (1904).
^Stoyan, Y. G.; Yaskov, G. N. (2010). "Packing identical spheres into a cylinder". International Transactions in Operational Research. 17: 51–70. doi:10.1111/j.1475-3995.2009.00733.x.
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 π/(32).[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 δ, 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δ 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 δ=VcontainerVobjects, where Vobjects is the total volume of packed objects and Vcontainer is the container volume; this can also be framed as the utilization ratioδ=1−fwaste, with the wastefractionfwaste=VcontainerVcontainer−Vobjects.[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 Λ such that the packing density Δ satisfies Δ≥2nζ(n), where ζ(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 Δ≲(n/e)⋅2−n/2 as n→∞.[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 Δ=π/12≈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 Δ≤2−0.599n(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.599n in high dimensions and remaining the strongest general upper bound for n≳[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 Ω(n) in n dimensions, yielding packings with center density δ≳n2⋅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 planeR2. 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δ=12π≈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 k1,k2,k3, the fourth has curvature k4=k1+k2+k3±2k1k2+k1k3+k2k3. Such packings exhibit fractal-like structure and achieve a radial density of 3/π≈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≤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 18π≈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 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 Δn is due to Kabatiansky and Levenshtein, who established that Δn≤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 E8 lattice in 8 dimensions, which achieves a density of 384π4≈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 12!π12≈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 cn22−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 Δ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 911\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 papermanufacturing, 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
These values derive from exhaustive searches and global optimization, with configurations visualized on dedicated packing databases.[44][46]
Packing unequal circles into a square or rectangle introduces additional complexity due to varying radii, often addressed through heuristic and metaheuristic algorithms to approximate minimal container sizes. Common approaches include greedy methods, such as the maximum hole degree heuristic, which iteratively places the next circle in the position maximizing local space utilization (defined as λ = 1 - dmin/ri, where dmin is the minimum distance to existing circles or boundaries and ri is the circle's radius), achieving densities up to 4.86% better than prior heuristics on benchmarks with 20–100 circles.[47] Population-based variants like basin hopping explore solution spaces by combining local optimization with global perturbations, improving results for instances with radii drawn from uniform distributions.[48]For practical implementations, raster methods discretize the container into a pixel grid to detect overlaps and guide placements, suitable for unequal circles treated as irregular shapes, while guillotine packings approximate solutions by recursively subdividing the rectangle into sub-rectangles and assigning circles to them, though less common for circles due to their curved boundaries.[2] Formulation space search heuristics, scaling circle radii to fit fixed containers like unit squares or rectangles (e.g., 10×1), further refine packings via mixed Cartesian-polar coordinates and swapping perturbations, outperforming earlier methods on test instances.[49]Waste minimization in these packings focuses on reducing unused space, formulated as minimizing the bounding box area A = s × w (square if s = w) subject to no overlaps, with density δ = Σ π ri2 / A. A basic lower bound for the square side length is s ≥ max(2 max ri, Σ 2 ri / k for some row count k), providing context for algorithmic performance without exhaustive enumeration.[50] Numerical results for up to 100 unequal circles show densities typically 0.7–0.85, depending on radius variance, with ongoing computations tracking records.[51]
Squares and rectangles in bins
Packing squares and rectangles into larger two-dimensional bins, often rectangular or square in shape, is a fundamental variant of the two-dimensional bin packing problem where items must be placed orthogonally without overlaps or rotations. This setup arises in applications such as cutting stock optimization in manufacturing and memory allocation in computer graphics, where the goal is to minimize wasted space or the number of bins used. Unlike circle packings, which require rotational freedom, rectangular items align naturally along axes, enabling structured algorithms like level and shelf packing that exploit horizontal or vertical slicing.[52]For equal squares packed into a larger square bin, the problem simplifies significantly when the number of unit squares n is a perfect square, n=k2 for integer k, allowing a trivial grid arrangement that achieves perfect density of 1 with no waste. In such cases, the side length of the bin is exactly k, and the packing is optimal by construction. For non-perfect squares, optimal packings become more complex, often requiring irregular arrangements to minimize the enclosing square's side length, as surveyed in early works on unit square packings. Known optimal densities approach 1 asymptotically but exhibit wasted space for specific n, such as the minimal side length exceeding n for n=2,3,5.[53][54]In the more general case of orthogonal packing of rectangles of varying sizes into bins, rotations are forbidden, and items must align with the bin's axes to avoid overlaps. Level algorithms, such as Next-Fit Decreasing Height (NFDH) and First-Fit Decreasing Height (FFDH), process rectangles sorted by decreasing height, placing them side-by-side on a horizontal "level" until the bin width is filled, then advancing to a new level. These methods produce guillotine-packable layouts, where the packing can be recursively partitioned by straight cuts parallel to the axes, facilitating efficient implementation in cutting processes. Guillotine constraints ensure that the entire bin can be divided into sub-rectangles via sequential full cuts, which is advantageous for manufacturability despite potentially lower densities compared to non-guillotine packings.[52][55]Shelf packing, a refinement of level algorithms, treats each horizontal strip as a "shelf" of fixed height equal to the tallest rectangle placed on it, packing subsequent items of equal or lesser height until the shelf is full. The FFDH shelf algorithm, when items are sorted by decreasing height, guarantees an approximation ratio of 2 for the strip packing variant, meaning the height used is at most twice the optimal, providing a practical bound for bin utilization in large instances. This 2-approximation holds asymptotically and has been foundational for subsequent improvements in two-dimensional packing heuristics.[52]
Irregular shapes in 2D
Packing irregular shapes in two dimensions involves arranging non-rectangular polygons, often non-convex, into a finite container such as a rectangle or strip to minimize waste while avoiding overlaps. Unlike regular shapes, these problems require handling arbitrary geometries, which complicates collision detection and optimization due to the need for precise spatial reasoning.[2]A key geometric tool for collision detection in these packings is the no-fit polygon (NFP), which defines the set of relative positions where one polygon would overlap with another if translated. Introduced by Art in 1966, the NFP enables efficient overlap checks by representing forbidden placements as a convex or non-convex boundary around a reference polygon.[56] Modern implementations, such as the complete and robust NFP generation algorithm, handle concave shapes and rotations by computing inner and outer fits, supporting fast placement decisions in heuristic and optimization frameworks.[57]Significant challenges arise from allowing rotations, which expand the search space exponentially, and shape fragmentation, where irregular boundaries create inefficient gaps that fragment the available space. These factors contribute to the NP-complete nature of the problem, often resulting in packing densities below 0.8 in practical benchmarks, such as those from the ESICUP dataset, where average densities range from 60% to 70% across standard irregular polygon sets.[2][58]A 2022 review highlights heuristic approaches like bottom-left (BL) strategies, which place shapes as far left and bottom as possible within the container, with variants such as improved BL and BL-fill enhancing density by considering fill order and rotations. Genetic algorithms have also been widely applied, encoding piece sequences and orientations as chromosomes, then evolving solutions through crossover and mutation to optimize utilization, often achieving 5-10% density improvements over naive placements in textile and sheet metal applications.[2][59]Recent advances, as of 2025, focus on decoupling geometric computations from optimization solvers using specialized collision detection engines (CDEs). These open-source tools, such as the one implemented in Rust for 2D irregular cutting and packing, handle all overlap and rotation checks independently, allowing standard optimizers like mixed-integer programming to focus solely on sequencing and assignment, thereby improving scalability for complex instances.[60] Such approaches briefly reference broader computational algorithms for hybrid solutions but emphasize modular design to reduce implementation barriers.[61]
Packings in three-dimensional containers
Spheres in cuboids or cylinders
Packing identical spheres into finite three-dimensional containers such as cuboids or cylinders introduces boundary constraints that influence the achievable packing density and arrangement compared to unbounded space. In cuboids, particularly cubes, optimal packings often employ layered structures akin to hexagonal close packing (HCP) or face-centered cubic (FCC) lattices, where spheres are arranged in successive planes with each sphere contacting up to 12 neighbors in the bulk. For large numbers of spheres n, these arrangements yield densities approaching approximately 0.74, the maximum for infinite three-dimensional sphere packings. However, exact optimal configurations remain computationally challenging, with improvements over simple cubic lattices achieved by omitting or translating spheres near boundaries to mitigate defects.Finite-size effects in cuboids significantly impact density due to boundary layers, where spheres near the walls experience reduced coordination and form less efficient structures, often lowering the overall packing fraction by 5-10% relative to the bulk value, especially in smaller containers. These effects arise from geometric mismatches between the lattice and container walls, leading to voids or distortions in the outer layers, with the reduction scaling inversely with system size as the surface-to-volume ratio decreases. A classic example is the cannonball problem, which considers stacking spheres into a square pyramidal arrangement within a cuboidal envelope, historically used to display cannonballs or oranges; this finite configuration demonstrates practical packing but achieves lower densities than full HCP due to the tapering shape and boundary constraints.[62]In cylindrical containers, packings favor straight columnar or helical arrangements, depending on the cylinderdiameter relative to sphere size. For narrow cylinders (diameter 2-4 times the sphere diameter), helical stackings—where spheres twist around the axis in quasiperiodic or chiral patterns—often maximize density by filling annular shells around a core column. Straight stackings, resembling linear HCP chains, dominate in wider cylinders. For an infinite cylinder, the optimal packing density matches the HCP limit of approximately 0.74, as the curvature becomes negligible and bulk arrangements prevail. Finite cylinders exhibit similar boundary reductions near the ends, though radial walls can induce more pronounced helical distortions for enhanced local density in confined regimes.
Cuboids into larger cuboids
The three-dimensional bin packing problem consists of orthogonally packing a set of smaller rectangular cuboids into the minimum number of identical larger cuboids, known as bins, such that no two cuboids overlap and all edges are aligned parallel to the bin's coordinate axes.[63] Orthogonal packing in this context permits rotations by multiples of 90 degrees to align dimensions with the bin but prohibits arbitrary orientations, facilitating efficient alignment and simplifying computational models.[63] This setup extends two-dimensional rectangle packing by adding a height dimension, which increases the geometric complexity of arrangement decisions.[64]The problem is strongly NP-hard, even when restricted to orthogonal packings, rendering exact solutions infeasible for large instances and motivating the development of approximation algorithms and heuristics.[63] A prominent heuristic is the Deepest Bottom Left with Fill (DBLF) method, which sequentially places each cuboid in the deepest feasible position relative to the current bottom-left corner of the available space, prioritizing depth to minimize gaps and enhance vertical stability before filling horizontally and laterally.[65] This approach often integrates with metaheuristics like genetic algorithms to iteratively refine placements, achieving high space utilization in practical scenarios such as container loading.[65]Guillotine packings impose an additional constraint where the final arrangement can be decomposed into a sequence of straight planar cuts parallel to the bin faces, each dividing a subregion completely; this structure is valuable in manufacturing and cutting stock applications, as it enables efficient production with guillotine shears or saws while maintaining orthogonal alignment.[66] Algorithms for guillotine-constrained 3D bin packing, such as those for unbounded knapsack and strip variants, solve these problems exactly for moderate sizes using dynamic programming over cut stages, though they sacrifice some flexibility compared to unrestricted orthogonal packings.[66]Theoretical bounds for orthogonal 3D bin packing include approximation algorithms with asymptotic ratios approaching 2.54 relative to the optimal number of bins, improving on prior ratios of about 2.86 and providing guarantees on solution quality for volume-based lower bounds.[67] These ratios imply that the wasted volume in the packing is bounded, typically allowing at least half the bin capacity to be utilized in the worst case, which establishes important context for scalability in optimization applications.[67]
Polyhedra in spheres or balls
Packing polyhedra into spheres or balls presents unique challenges compared to rectangular containers, as the curved boundary necessitates careful orientation and positioning to minimize wasted space near the surface. This problem is particularly studied for Platonic solids, which are regular convex polyhedra, due to their symmetry and uniform faces. Finite packings in spherical confinement often draw inspiration from infinite-space arrangements but require adjustments for boundary effects, such as rotational optimizations to align edges and vertices with the sphere's curvature. Monte Carlo simulations have been employed to identify dense configurations, revealing that Platonic solids tend to form layered structures resembling optimal spherical codes at certain "magic numbers" of particles, where density peaks due to enhanced symmetry.[68]For regular tetrahedra, small-number packings in spheres highlight local geometric constraints. An arrangement of 5 tetrahedra sharing a common edge achieves near-optimal local density, with each tetrahedron's dihedral angle of approximately 70.53° leaving a small angular gap of 7.36°, which can be minimized through slight distortions in finite spherical settings, as observed in self-assembled nanoparticle structures with 5-fold symmetry. This icosahedral-like configuration maximizes coordination around the shared edge while fitting within a minimal enclosing sphere. Larger finite packings, such as n=22, form denser clusters with two pentagonal dipyramids and face-to-face dimers, but overall similarity to sphere packings remains low for tetrahedra due to their sharp angles.[69][70][68]Cubes, being the only space-filling Platonic solid, adapt face-centered arrangements in spherical containers to approximate high-density lattice packings. In a sphere, cubes can be layered in a manner analogous to the face-centered cubic lattice used for spheres, with each cube surrounded by up to 12 neighbors in optimal infinite configurations, though boundary constraints reduce this in finite cases. Simulations show dense cube clusters at magic numbers like n=7 and n=21, but only a few arrangements closely mimic sphere packing densities, emphasizing the need for orthogonal alignments to avoid overhangs beyond the spherical hull. The kissing number of 6 for cubes—limited to face-adjacent contacts—further constrains local density in curved spaces.[68][71]Packings of other Platonic solids, such as dodecahedra, benefit from their icosahedral symmetry in spherical confinement. In infinite space, the densest known packing of regular dodecahedra achieves a density of approximately 0.904 through non-lattice arrangements, but finite spherical packings require adjustments, often yielding peaks at n=13 and n=25 with layered spherical code structures. These configurations frequently resemble optimal sphere packings, with up to three concentric layers forming the cluster's convex hull. Challenges in such packings include managing the convex hull to ensure containment within the sphere and adhering to kissing numbers, such as 20 for tetrahedra or icosahedra, where angular deficits around vertices (e.g., 7.36° gaps in tetrahedral coordination) necessitate distortions for higher densities without overlap.[72][68][73]
Irregular and advanced packing problems
Challenges with non-convex objects
Packing non-convex objects in three-dimensional space introduces significant geometric challenges compared to convex counterparts, primarily due to their irregular shapes that can lead to interlocking, where objects become mechanically trapped in configurations that prevent easy rearrangement or removal.[74] Voids, or unoccupied spaces that are difficult to fill because of concave features, further complicate achieving high packing densities, as these indentations create inefficient gaps between objects.[74] For instance, concave polyhedra, such as those with reentrant surfaces or cavities, exacerbate these issues by allowing partial overlaps or unstable nestings that violate non-overlap constraints during placement.[75]To address these challenges, voxelization discretizes non-convex objects into a grid of small cubic elements (voxels), enabling efficient overlap detection through constructs like the nofit voxel, which maps relative positions where intersections occur.[76] This approach approximates complex geometries, such as blobs with holes or engine parts, allowing optimization techniques like integer linear programming or metaheuristics to minimize container volume while handling non-convexity.[76] Similarly, phi-functions provide an analytical tool for modeling feasibility by defining continuous, differentiable expressions that describe non-overlapping and containment constraints between objects, particularly useful for irregular shapes where exact boundary interactions must be ensured without approximation errors.[77]A recent advancement, the Packing of Objects Composed by Generalized Spheres (PCGS) framework introduced in 2024, reduces the problem of packing non-convex irregular objects to a generalized sphere packing variant by representing each object as a union of spheres defined under an arbitrary norm, thereby leveraging established sphere packing algorithms while accommodating concavities through norm flexibility.[78]Due to these inherent shape complexities, packing densities for non-convex 3D objects are typically limited to below 0.6, with benchmarks for generic irregular forms often achieving around 0.36 to 0.44, far short of the 0.74 attainable for spheres.[79]
Computational approaches and algorithms
Computational approaches to packing problems encompass a range of exact and heuristic methods tailored to the dimensionality and complexity of the instances. Exact methods, such as branch-and-bound algorithms, are effective for solving small-scale problems where optimality is required, systematically exploring the solution space by branching on decision variables and bounding suboptimal paths. For instance, branch-and-bound has been applied to orthogonal packing in higher dimensions, achieving exact solutions for instances with up to dozens of items by leveraging geometric constraints and linear relaxations.[80] Mixed-integer programming (MIP) formulations provide another exact avenue, modeling packing as optimization problems with integer variables for item assignments and continuous variables for positions, solvable via commercial solvers like CPLEX or Gurobi for moderate-sized rectangular packing tasks.[81]Metaheuristics offer scalable alternatives for larger or irregular packing instances, where exact methods become computationally prohibitive. Genetic algorithms (GAs), inspired by natural evolution, encode packing layouts as chromosomes and evolve populations through selection, crossover, and mutation to minimize wasted space; seminal work demonstrated their efficacy for bin packing by grouping similar items to improve density.[82]Simulated annealing (SA), mimicking metallurgical cooling, perturbs current solutions probabilistically to escape local optima, proving particularly useful for irregular strip packing by hybridizing with local searches to handle non-convex shapes.[83] These approaches often reference simpler heuristics like first-fit decreasing (FFD) from one-dimensional cases to initialize solutions, adapting them for multi-dimensional extensions.[84]Recent advancements in 2025 incorporate AI-driven techniques, leveraging deep learning for pattern recognition in 2D and 3D packing. Transformer-based models, integrated within reinforcement learning frameworks, generate placement heuristics for online 2D strip packing, processing item sequences to predict efficient arrangements with reduced computational overhead compared to traditional metaheuristics.[85]Deep reinforcement learning (DRL) frameworks train agents to optimize 3D multi-bin packing by rewarding dense configurations, achieving improved utilization on benchmark datasets.[86]Practical implementations are supported by specialized software tools. SVGnest, an open-source library for 2D nesting, employs genetic algorithms with no-fit polygon generation to pack irregular vector shapes efficiently, enabling part-in-part nesting for manufacturing applications.[87] General optimizers like Google's OR-Tools provide constraint programming and MIP solvers for various packing variants, including 1D bin packing and 2D knapsack problems, with extensible APIs for custom 3D extensions.[88]
Applications and related fields
In optimization and computer science
Packing problems, particularly bin packing variants, are central to optimization and computer science due to their computational complexity and relevance to resource allocation. The classical one-dimensional bin packing problem is strongly NP-hard, and this hardness extends to higher dimensions. Specifically, the two-dimensional orthogonal bin packing problem, where rectangles must be packed into square bins without rotations, is NP-hard.[89] Even the restricted case of packing squares into square bins remains NP-hard.[90] In three dimensions, the problem of packing cuboids into larger cuboids is also NP-hard, with inapproximability results showing it cannot be approximated within a factor better than 1.5 unless P=NP.[90]Approximation algorithms provide practical solutions for these intractable problems. For two-dimensional rectangle bin packing, early approximation schemes in the 1990s achieved constant factors, such as the 2-approximation via level-oriented packing.[91] Subsequent developments include asymptotic polynomial-time approximation schemes (APTAS), which guarantee packings using at most (1+ε)OPT + c/ε bins for small ε>0 and constant c, though no exact PTAS exists due to APX-hardness.[92] For irregular shapes, where items have non-rectangular geometries, approximation is more challenging, but recent heuristics offer strong empirical performance. In 2024, the Knowledge Reuse and Improved Heuristic (KRIH) algorithm for irregular bin packing demonstrated robustness by achieving better or equal solutions than classical methods on 8 of 16 benchmark instances, often in shorter computation times.[93]Key variants extend the core problem to richer settings. Vector bin packing generalizes to d dimensions, where items and bins are vectors, and packing requires no coordinate exceeding capacity; it is NP-hard for d≥2, with approximation ratios improving to O(log d / log log d) via iterative rounding techniques.[94] The multiple knapsack problem, a close relative, involves assigning items to multiple heterogeneous knapsacks to maximize total value without exceeding capacities per knapsack; it admits a PTAS, achieving (1-ε)-optimal solutions in polynomial time.[95] These variants model applications like cloud resource allocation, where multidimensional constraints arise.Computational methods, such as branch-and-price or metaheuristics, often integrate with these approximations to handle large-scale instances efficiently.
In physics and materials science
In crystallography, efficient atomic packing in lattice structures underpins the stability and properties of crystalline solids. The face-centered cubic (FCC) lattice, common in metals such as copper, aluminum, and gold, represents an optimal ordered packing arrangement with a density of π/18≈0.74, where atoms occupy 74% of the available volume.[96] This close-packing efficiency arises from each atom being surrounded by 12 nearest neighbors, maximizing space utilization while minimizing voids, and it directly influences material density, ductility, and thermal conductivity.[97] Similarly, the hexagonal close-packed (HCP) structure, adopted by metals like magnesium and titanium, achieves the same 0.74 packing density through layered arrangements that mirror FCC geometry.[97]In granular materials, such as sands, powders, or beads, packing problems are explored through disordered configurations rather than perfect lattices, with random close packing (RCP) serving as a key benchmark. For monodisperse spheres, RCP yields a packing density of approximately 0.64, below the 0.74 of ordered FCC lattices, representing the highest achievable density in random, jammed states without crystallization.[98] This value emerges from experimental protocols like gentle shaking or sedimentation, where particle friction and collisions prevent denser arrangements, and it critically affects flowability, porosity, and stress transmission in applications ranging from soil mechanics to pharmaceutical tablet formulation.[99]Jamming transitions in granular packings describe the abrupt shift from a fluid-like, flowing state to a rigid, solid-like state as density increases, typically occurring near the RCP threshold of 0.64 for spheres. In these athermal systems, jamming involves the emergence of rigid contacts and isostaticity, where the average number of contacts per particle reaches a critical value (around 6 for frictionless spheres), halting collective motion and enabling load-bearing.[100] This transition, studied via simulations and experiments on frictional and frictionless grains, reveals universal scaling behaviors in mechanical properties and has implications for understanding earthquakes, avalanches, and the rheology of dense suspensions.[101]In nanotechnology, DNA origami facilitates custom packings by programming DNA strands to self-assemble into precise two- and three-dimensional nanostructures, overcoming traditional limitations in molecular arrangement.[102] This technique, pioneered for creating scaffolds with sub-nanometer precision, enables the design of lattices and cages that mimic efficient packings for encapsulating nanoparticles or biomolecules, enhancing stability in drug delivery and sensing devices.[103] As of 2025, recent advances include DNA origami designs for enhanced nuclear gene delivery and precise protein folding studies using force spectroscopy.[104][105]
.svg)
