Packing problems
Covering/packingproblem pairs  



Part of a series on 
Puzzles 

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.
In a bin packing problem, you are given:
 'containers' (usually a single two or threedimensional convex region, or an infinite space)
 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 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.
Contents
Packing infinite space[edit]
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]} and unequalsphere dimers.^{[6]}
Hexagonal packing of circles[edit]
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 onedimensional universe, the circle analogue is just two points). That is, there will always be unused space if you are only packing circles. The most efficient way of packing circles, hexagonal packing, produces approximately 91% efficiency.^{[7]}
Sphere packings in higher dimensions[edit]
In three dimensions, the facecentered cubic lattice offers 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 defineable packings.^{[8]} The 8dimensional E8 lattice and 24dimensional Leech lattice have also been proven to be optimal in their respective real dimensional space.
Packings of Platonic solids in three dimensions[edit]
Cubes can easily be arranged to fill threedimensional 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 facecentered cubic (FCC) lattice.
Tetrahedra and octahedra together can fill all of space in an arrangement known as the tetrahedraloctahedral honeycomb.
Solid  Optimal density of a lattice packing 

icosahedron  0.836357...^{[9]} 
dodecahedron  (5 + √5)/8 = 0.904508...^{[9]} 
octahedron  18/19 = 0.947368...^{[10]} 
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]}
Packing in 3dimensional containers[edit]
Different cuboids into a cuboid[edit]
Determine the minimum number of cuboid containers (bins) that are required to pack a given set of item cuboids (3 Dimensional rectangles). The rectangular cuboids to be packed can be rotated by 90 degrees on each axis.
Spheres into a Euclidean ball[edit]
The problem of finding the smallest ball such that disjoint open unit balls may be packed inside it has a simple and complete answer in 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 pairwise tangent unit balls is available. 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 vertices. In terms of inclusions of balls, the 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 disjoint open unit balls contained in a ball of radius centered at a point . Consider the map from the finite set into taking in the corresponding for each . Since for all , this map is 1Lipschitz and by the Kirszbraun theorem it extends to a 1Lipschitz 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 disjoint unit open balls in a ball of radius if 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 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 .
Spheres in a cuboid[edit]
Determine the number of spherical objects of given diameter d can be packed into a cuboid of size a × b × c.
Identical spheres in a cylinder[edit]
Determine the minimum height h of a cylinder with given radius R that will pack n identical spheres of radius r (< R).^{[11]}
Polyhedra in spheres[edit]
Determine the minimum radius R that will pack n identical, unit volume polyhedra of a given shape.^{[12]}
Packing in 2dimensional containers[edit]
Packing circles[edit]
Circles in circle[edit]
Pack n unit circles into the smallest possible circle. This is closely related to spreading points in a unit circle with the objective of finding the greatest minimal separation, d_{n}, between points.
Optimal solutions have been proven for n ≤ 13, and n = 19.
Circles in square[edit]
Pack n unit circles into the smallest possible square. This is closely related to spreading points in a unit square with the objective of finding the greatest minimal separation, d_{n}, between points.^{[13]} To convert between these two formulations of the problem, the square side for unit circles will be L = 2 + 2/d_{n}.
Optimal solutions have been proven for n ≤ 30.^{[14]}
Circles in isosceles right triangle[edit]
Pack n unit circles into the smallest possible isosceles right triangle. Good estimates are known for n<300.^{[15]}
Circles in equilateral triangle[edit]
Pack n unit circles into the smallest possible equilateral triangle. Optimal solutions are known for n<13, and conjectures are available for n < 28.^{[16]}
Packing squares[edit]
Squares in square[edit]
Pack n unit squares into the smallest possible square.
Optimal solutions have been proven for n = 1–10, 14–16, 22–25, 33–36, 62–64, 79–81, 98–100, and any square integer.^{[17]}^{[18]}
The wasted space is asymptotically O(a^{7/11}).^{[19]}
Squares in circle[edit]
Pack n squares in the smallest possible circle.
Minimum solutions:^{[20]}
Number of squares  Circle radius 

1  0.707... 
2  1.118... 
3  1.288... 
4  1.414... 
5  1.581... 
6  1.688... 
7  1.802... 
8  1.978... 
9  2.077... 
10  2.121... 
11  2.214... 
12  2.236... 
Packing rectangles[edit]
Identical rectangles in a rectangle[edit]
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).^{[21]}
Different rectangles in a rectangle[edit]
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.
An example of a fast algorithm that packs rectangles of varying widths and heights into an enclosing rectangle of minimum area is here.
Related fields[edit]
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 squarelike 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 iff n divides a or n divides b.^{[22]}^{[23]}
 de Bruijn's theorem: A box can be packed with a harmonic brick a × a b × a b c if the box has dimensions a p × a b q × a b c r for some natural numbers p, q, r (i.e., the box is a multiple of the brick.)^{[22]}
The study of polyomino tilings largely concerns two classes of problems: to tile a rectangle with congruent tiles, and to pack one of each nomino 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[edit]
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.^{[24]}
See also[edit]
 Set packing
 Bin packing problem
 Slothouber–Graatsma puzzle
 Conway puzzle
 Tetris
 Covering problem
 Knapsack problem
 Tetrahedron packing
 Cutting stock problem
 Kissing number problem
 Closepacking of equal spheres
 Random close pack
Notes[edit]
 ^ Lodi, A., Martello, S., Monaci, M. (2002). "Twodimensional packing problems: A survey". European Journal of Operational Research. Elsevier. 141: 241–252. doi:10.1016/s03772217(02)001236.
 ^ Donev, A.; Stillinger, F.; Chaikin, P.; Torquato, S. (2004). "Unusually Dense Crystal Packings of Ellipsoids". Physical Review Letters. 92 (25): 255506. arXiv:condmat/0403286. Bibcode:2004PhRvL..92y5506D. doi:10.1103/PhysRevLett.92.255506. PMID 15245027.
 ^ ^{a} ^{b} Torquato, S.; Jiao, Y. (Aug 2009). "Dense packings of the Platonic and Archimedean solids". Nature. 460 (7257): 876–879. arXiv:0908.4107. Bibcode:2009Natur.460..876T. doi:10.1038/nature08239. ISSN 00280836. PMID 19675649.
 ^ HajiAkbari, A.; Engel, M.; Keys, A. S.; Zheng, X.; Petschek, R. G.; PalffyMuhoray, P.; Glotzer, S. C. (2009). "Disordered, quasicrystalline and crystalline phases of densely packed tetrahedra". Nature. 462 (7274): 773–777. arXiv:1012.5138. Bibcode:2009Natur.462..773H. doi:10.1038/nature08641. PMID 20010683.
 ^ Chen, E. R.; Engel, M.; Glotzer, S. C. (2010). "Dense Crystalline Dimer Packings of Regular Tetrahedra". Discrete & Computational Geometry. 44 (2): 253–280. arXiv:1001.0586. doi:10.1007/s0045401092730.
 ^ Hudson, T. S.; Harrowell, P. (2011). "Structural searches using isopointal sets as generators: Densest packings for binary hard sphere mixtures". Journal of Physics: Condensed Matter. 23 (19): 194103. Bibcode:2011JPCM...23s4103H. doi:10.1088/09538984/23/19/194103.
 ^ http://mathworld.wolfram.com/CirclePacking.html
 ^ Smalley, I.J. 1963. Simple regular sphere packings in three dimensions. Mathematics Magazine 36, 295299. doi:10.2307/2688954
 ^ ^{a} ^{b} Betke, U. & Henk, M. Densest lattice packings of 3polytopes. Comput. Geom. 16, 157–186 (2000)
 ^ Minkowski, H. Dichteste gitterfo¨rmige Lagerung kongruenter Ko¨rper. Nachr. Akad. Wiss. Go¨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.14753995.2009.00733.x.
 ^ Teich, E.G.; van Anders, G.; Klotsa, D.; Dshemuchadse, J.; Glotzer, S.C. (2016). "Clusters of Polyhedra in Spherical Confinement". Proc. Natl. Acad. Sci. U.S.A. 113: E669–E678. doi:10.1073/pnas.1524875113.
 ^ Croft, Hallard T.; Falconer, Kenneth J.; Guy, Richard K. (1991). Unsolved Problems in Geometry. New York: SpringerVerlag. pp. 108–110. ISBN 0387975063.
 ^ Eckard Specht (20 May 2010). "The best known packings of equal circles in a square". Retrieved 25 May 2010.
 ^ Specht, Eckard (11 March 2011). "The best known packings of equal circles in an isosceles right triangle". Retrieved 1 May 2011.
 ^ Melissen, J. (1995). "Packing 16, 17 or 18 circles in an equilateral triangle". Discrete Mathematics. 145: 333–342. doi:10.1016/0012365X(95)90139C.
 ^ Erich Friedman, "Packing unit squares in squares: a survey and new results" Archived 27 July 2009 at the Wayback Machine., The Electronic Journal of Combinatorics DS7 (2005).
 ^ Wolfram Bentz (12 June 2016). "Optimal Packings of 22 and 33 Unit Squares in a Square". arXiv:1606.03746. Bibcode:2016arXiv160603746B.
 ^ Erdős, P.; Graham, R. L. (1975). "On packing squares with equal squares" (PDF). Journal of Combinatorial Theory, Series A. 19: 119–123. doi:10.1016/00973165(75)900990.
 ^ http://www2.stetson.edu/~efriedma/squincir/
 ^ Birgin, E G; Lobato, R D; Morabito, R (2010). "An effective recursive partitioning approach for the packing of identical rectangles in a rectangle". Journal of the Operational Research Society. 61: 306–320. doi:10.1057/jors.2008.141.
 ^ ^{a} ^{b} Honsberger, Ross (1976). Mathematical Gems II. The Mathematical Association of America. p. 67. ISBN 0883853027.
 ^ Klarner, D.A.; Hautus, M.L.J (1971). "Uniformly coloured stained glass windows". Proceedings of the London Mathematical Society. 3. 23: 613–628. doi:10.1112/plms/s323.4.613.
 ^ C.Michael Hogan. 2010. Abiotic factor. Encyclopedia of Earth. eds Emily Monosson and C. Cleveland. National Council for Science and the Environment. Washington DC
References[edit]
 Weisstein, Eric W. "Klarner's Theorem". MathWorld.
 Weisstein, Eric W. "de Bruijn's Theorem". MathWorld.
External links[edit]
 Optimizing ThreeDimensional Bin Packing
 API for 3D bin packing
 3D Boxes and Cylinders packing with telescoping
Many puzzle books as well as mathematical journals contain articles on packing problems.
 Links to various MathWorld articles on packing
 MathWorld notes on packing squares.
 Erich's Packing Center
 www.packomania.com A site with tables, graphs, calculators, references, etc.
 "Box Packing" by Ed Pegg, Jr., the Wolfram Demonstrations Project, 2007.
 Best known packings of equal circles in a circle, up to 1100