Packing problems

Last updated
Spheres or circles packed loosely (top) and more densely (bottom) Seissand.png
Spheres or circles packed loosely (top) and more densely (bottom)

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.

Contents

In a bin packing problem, people are given:

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.

Packing in infinite space

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]

Hexagonal packing of circles

The hexagonal packing of circles on a 2-dimensional Euclidean plane. Circle packing (hexagonal).svg
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]

Sphere packings in higher dimensions

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.

Packings of Platonic solids in three dimensions

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.

Tetrahedra and octahedra together can fill all of space in an arrangement known as the tetrahedral-octahedral honeycomb.

SolidOptimal density of a lattice packing
icosahedron 0.836357... [10]
dodecahedron(5+5)/8 = 0.904508... [10]
octahedron18/19 = 0.947368... [11]

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 3-dimensional containers

Packing nine L tricubes into a cube 9L cube puzzle solution.svg
Packing nine L tricubes into a cube

Different cuboids into a cuboid

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.

Spheres into a Euclidean ball

The problem of finding the smallest ball such that k disjoint 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 r 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 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 .

Spheres in a cuboid

People determine the number of spherical objects of given diameter d that can be packed into a cuboid of size .

Identical spheres in a cylinder

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.

Polyhedra in spheres

People determine the minimum radius R that will pack n identical, unit volume polyhedra of a given shape. [13]

Packing in 2-dimensional containers

The optimal packing of 10 circles in a circle Disk pack10.svg
The optimal packing of 10 circles in a circle

Many variants of 2-dimensional packing problems have been studied.

Packing of circles

People are given n unit circles, and have to pack them in the smallest possible container. Several kinds of containers have been studied:

Packing of squares

People are given n unit squares and have to pack them into the smallest possible container, where the container type varies:

Packing of rectangles

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]
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.) [15]

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

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]

The problem of deciding whether a given set of polygons can fit in a given square container has been shown to be complete for the existential theory of the reals. [18]

See also

Notes

  1. Lodi, A.; Martello, S.; Monaci, M. (2002). "Two-dimensional packing problems: A survey". European Journal of Operational Research. 141 (2). Elsevier: 241–252. doi:10.1016/s0377-2217(02)00123-6.
  2. Donev, A.; Stillinger, F.; Chaikin, P.; Torquato, S. (2004). "Unusually Dense Crystal Packings of Ellipsoids". Physical Review Letters. 92 (25): 255506. arXiv: cond-mat/0403286 . Bibcode:2004PhRvL..92y5506D. doi:10.1103/PhysRevLett.92.255506. PMID   15245027. S2CID   7982407.
  3. 1 2 Torquato, S.; Jiao, Y. (August 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   0028-0836. PMID   19675649. S2CID   52819935.
  4. Haji-Akbari, A.; Engel, M.; Keys, A. S.; Zheng, X.; Petschek, R. G.; Palffy-Muhoray, 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. S2CID   4412674.
  5. 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 . Bibcode:2010arXiv1001.0586C. doi: 10.1007/s00454-010-9273-0 . S2CID   18523116.
  6. Stein, Sherman K. (March 1995), "Packing tripods", Mathematical entertainments, The Mathematical Intelligencer , 17 (2): 37–39, doi:10.1007/bf03024896, S2CID   124703268 . Reprinted in Gale, David (1998), Gale, David (ed.), Tracking the Automatic ANT, Springer-Verlag, pp. 131–136, doi:10.1007/978-1-4612-2192-0, ISBN   0-387-98272-8, MR   1661863
  7. 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/0953-8984/23/19/194103. PMID   21525553. S2CID   25505460.
  8. "Circle Packing".
  9. Smalley, I.J. (1963). "Simple regular sphere packings in three dimensions". Mathematics Magazine. 36 (5): 295–299. doi:10.2307/2688954. JSTOR   2688954.
  10. 1 2 Betke, Ulrich; Henk, Martin (2000). "Densest lattice packings of 3-polytopes". Computational Geometry . 16 (3): 157–186. arXiv: math/9909172 . doi: 10.1016/S0925-7721(00)00007-9 . MR   1765181. S2CID   12118403.
  11. Minkowski, H. Dichteste gitterförmige Lagerung kongruenter Körper. Nachr. Akad. Wiss. Göttingen Math. Phys. KI. II 311–355 (1904).
  12. 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.
  13. 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 (6): E669–E678. Bibcode:2016PNAS..113E.669T. doi: 10.1073/pnas.1524875113 . PMC   4760782 . PMID   26811458.
  14. Melissen, J. (1995). "Packing 16, 17 or 18 circles in an equilateral triangle". Discrete Mathematics. 145 (1–3): 333–342. doi: 10.1016/0012-365X(95)90139-C .
  15. 1 2 Honsberger, Ross (1976). Mathematical Gems II. The Mathematical Association of America. p. 67. ISBN   0-88385-302-7.
  16. Klarner, D.A.; Hautus, M.L.J (1971). "Uniformly coloured stained glass windows". Proceedings of the London Mathematical Society. 3. 23 (4): 613–628. doi:10.1112/plms/s3-23.4.613.
  17. C.Michael Hogan. 2010. Abiotic factor. Encyclopedia of Earth. eds Emily Monosson and C. Cleveland. National Council for Science and the Environment. Washington DC
  18. Abrahamsen, Mikkel; Miltzow, Tillmann; Nadja, Seiferth (2020), Framework for -Completeness of Two-Dimensional Packing Problems, arXiv: 2004.07558 .

Related Research Articles

<span class="mw-page-title-main">Ball (mathematics)</span> Volume space bounded by a sphere

In mathematics, a ball is the solid figure bounded by a sphere; it is also called a solid sphere. It may be a closed ball or an open ball.

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, splitting a network prefix into multiple subnets, and technology mapping in FPGA semiconductor chip design.

<span class="mw-page-title-main">Sphere packing</span> Geometrical structure

In geometry, a sphere packing is an arrangement of non-overlapping spheres within a containing space. The spheres considered are usually all of identical size, and the space is usually three-dimensional Euclidean space. However, sphere packing problems can be generalised to consider unequal spheres, spaces of other dimensions or to non-Euclidean spaces such as hyperbolic space.

In geometry, the kissing number of a mathematical space is defined as the greatest number of non-overlapping unit spheres that can be arranged in that space such that they each touch a common unit sphere. For a given sphere packing in a given space, a kissing number can also be defined for each individual sphere as the number of spheres it touches. For a lattice packing the kissing number is the same for every sphere, but for an arbitrary sphere packing the kissing number may vary from one sphere to another.

<span class="mw-page-title-main">Minkowski–Bouligand dimension</span> Method of determining fractal dimension

In fractal geometry, the Minkowski–Bouligand dimension, also known as Minkowski dimension or box-counting dimension, is a way of determining the fractal dimension of a set in a Euclidean space , or more generally in a metric space . It is named after the Polish mathematician Hermann Minkowski and the French mathematician Georges Bouligand.

<span class="mw-page-title-main">Close-packing of equal spheres</span> Dense arrangement of congruent spheres in an infinite, regular arrangement

In geometry, close-packing of equal spheres is a dense arrangement of congruent spheres in an infinite, regular arrangement. Carl Friedrich Gauss proved that the highest average density – that is, the greatest fraction of space occupied by spheres – that can be achieved by a lattice packing is

In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of all possible words. It gives an important limitation on the efficiency with which any error-correcting code can utilize the space in which its code words are embedded. A code that attains the Hamming bound is said to be a perfect code.

<span class="mw-page-title-main">Guillotine cutting</span> Process of producing small rectangular items of fixed dimensions

Guillotine cutting is the process of producing small rectangular items of fixed dimensions from a given large rectangular sheet, using only guillotine-cuts. A guillotine-cut is a straight bisecting line going from one edge of an existing rectangle to the opposite edge, similarly to a paper guillotine.

<span class="mw-page-title-main">Hyperplane separation theorem</span> On the existence of hyperplanes separating disjoint convex sets

In geometry, the hyperplane separation theorem is a theorem about disjoint convex sets in n-dimensional Euclidean space. There are several rather similar versions. In one version of the theorem, if both these sets are closed and at least one of them is compact, then there is a hyperplane in between them and even two parallel hyperplanes in between them separated by a gap. In another version, if both disjoint convex sets are open, then there is a hyperplane in between them, but not necessarily any gap. An axis which is orthogonal to a separating hyperplane is a separating axis, because the orthogonal projections of the convex bodies onto the axis are disjoint.

In mathematics, the Vitali covering lemma is a combinatorial and geometric result commonly used in measure theory of Euclidean spaces. This lemma is an intermediate step, of independent interest, in the proof of the Vitali covering theorem. The covering theorem is credited to the Italian mathematician Giuseppe Vitali. The theorem states that it is possible to cover, up to a Lebesgue-negligible set, a given subset E of Rd by a disjoint family extracted from a Vitali covering of E.

In mathematics, the packing dimension is one of a number of concepts that can be used to define the dimension of a subset of a metric space. Packing dimension is in some sense dual to Hausdorff dimension, since packing dimension is constructed by "packing" small open balls inside the given subset, whereas Hausdorff dimension is constructed by covering the given subset by such small open balls. The packing dimension was introduced by C. Tricot Jr. in 1982.

<span class="mw-page-title-main">Circle packing theorem</span> Describes the possible tangency relations between circles with disjoint interiors

The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint. The intersection graph of a circle packing is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent. If the circle packing is on the plane, or, equivalently, on the sphere, then its intersection graph is called a coin graph; more generally, intersection graphs of interior-disjoint geometric objects are called tangency graphs or contact graphs. Coin graphs are always connected, simple, and planar. The circle packing theorem states that these are the only requirements for a graph to be a coin graph:

<span class="mw-page-title-main">Circle packing</span> Field of geometry closely arranging circles on a plane

In geometry, circle packing is the study of the arrangement of circles on a given surface such that no overlapping occurs and so that no circle can be enlarged without creating an overlap. The associated packing density, η, of an arrangement is the proportion of the surface covered by the circles. Generalisations can be made to higher dimensions – this is called sphere packing, which usually deals only with identical spheres.

In mathematics, a covering number is the number of balls of a given size needed to completely cover a given space, with possible overlaps between the balls. The covering number quantifies the size of a set and can be applied to general metric spaces. Two related concepts are the packing number, the number of disjoint balls that fit in a space, and the metric entropy, the number of points that fit in a space when constrained to lie at some fixed minimum distance apart.

In mathematics, a unit sphere is a sphere of unit radius: the set of points at Euclidean distance 1 from some center point in three-dimensional space. More generally, the unit -sphere is an -sphere of unit radius in -dimensional Euclidean space; the unit circle is a special case, the unit -sphere in the plane. An (open) unit ball is the region inside of a unit sphere, the set of points of distance less than 1 from the center.

Square packing is a packing problem where the objective is to determine how many congruent squares can be packed into some larger shape, often a square or circle.

A geometric separator is a line that partitions a collection of geometric shapes into two subsets, such that proportion of shapes in each subset is bounded, and the number of shapes that do not belong to any subset is small.

In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.

<span class="mw-page-title-main">Tripod packing</span>

In combinatorics, tripod packing is a problem of finding many disjoint tripods in a three-dimensional grid, where a tripod is an infinite polycube, the union of the grid cubes along three positive axis-aligned rays with a shared apex.

In mathematics, the theory of finite sphere packing concerns the question of how a finite number of equally-sized spheres can be most efficiently packed. The question of packing finitely many spheres has only been investigated in detail in recent decades, with much of the groundwork being laid by László Fejes Tóth.

References

Many puzzle books as well as mathematical journals contain articles on packing problems.