Packing problems: Difference between revisions

Revision as of 02:27, 13 September 2021

Revision as of 17:47, 24 April 2022

Line 1:

{{about|geometric packing problems|numerical packing problems|Knapsack problem}}

[[File:Seissand.png|thumb|Spheres[[Sphere]]s or circles[[circle]]s packed loosely (top) and more densely (bottom)]]

{{Covering/packing-problem pairs}}

{{Puzzles |topics}}

Line 7:

In a [[bin packing problem]], you are given:

* 'containers' (usually a single two- or three-dimensional [[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.

Line 13:

==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 [[sphere packing|packing spheres]] hundreds of years before it was [[mathematical proof|proven]] correct by [[Thomas Callister Hales]]. Many other shapes have received attention, including ellipsoids,<ref>{{Cite journal | last1 = Donev | first1 = A. | last2 = Stillinger | first2 = F. | last3 = Chaikin | first3 = P. | last4 = Torquato | first4 = S. | title = Unusually Dense Crystal Packings of Ellipsoids | doi = 10.1103/PhysRevLett.92.255506 | journal = Physical Review Letters | volume = 92 | issue = 25 | year = 2004 | pmid = 15245027|arxiv = cond-mat/0403286 |bibcode = 2004PhRvL..92y5506D | page=255506| s2cid = 7982407 }}</ref> [[Platonic solid|Platonic]] and [[Archimedean solidssolid]]s<ref name="Torquato"/> including [[tetrahedron packing|tetrahedra]],<ref>{{Cite journal | doi = 10.1038/nature08641 | last1 = Haji-Akbari | first1 = A. | last2 = Engel | first2 = M. | last3 = Keys | first3 = A. S. | last4 = Zheng | pmid = 20010683 | first4 = X. | last5 = Petschek | first5 = R. G. | last6 = Palffy-Muhoray | first6 = P. | last7 = Glotzer | first7 = S. C. | title = Disordered, quasicrystalline and crystalline phases of densely packed tetrahedra | year = 2009 | journal = Nature | volume = 462 | issue = 7274 | pages = 773–777 |bibcode = 2009Natur.462..773H |arxiv = 1012.5138 | s2cid = 4412674 }}</ref><ref>{{Cite journal | last1 = Chen | first1 = E. R. | last2 = Engel | first2 = M. | last3 = Glotzer | first3 = S. C. | title = Dense Crystalline Dimer Packings of Regular Tetrahedra | journal = [[Discrete & Computational Geometry]] | volume = 44 | issue = 2 | pages = 253–280 | year = 2010 | doi = 10.1007/s00454-010-9273-0| doi-access=free | arxiv = 1001.0586 | bibcode = 2010arXiv1001.0586C | s2cid = 18523116 }}</ref> [[Tripod packing|tripods]] (unions of cubes[[cube]]s along three positive axis-parallel rays),<ref>{{citation|last=Stein|first=Sherman K.|author-link= Sherman K. Stein |date=March 1995|department=Mathematical entertainments|doi=10.1007/bf03024896|issue=2|journal=[[The Mathematical Intelligencer]]|pages=37–39|title=Packing tripods|volume=17|s2cid=124703268}}. Reprinted in {{citation|last=Gale|first=David|editor1-first=David|editor1-last=Gale|doi=10.1007/978-1-4612-2192-0|isbn=0-387-98272-8|mr=1661863|pages=131–136|publisher=Springer-Verlag|title=Tracking the Automatic ANT|year=1998}}</ref> and unequal-sphere dimers.<ref>{{Cite journal | last1 = Hudson | first1 = T. S. | last2 = Harrowell | first2 = P. | doi = 10.1088/0953-8984/23/19/194103 | pmid = 21525553 | title = Structural searches using isopointal sets as generators: Densest packings for binary hard sphere mixtures | journal = Journal of Physics: Condensed Matter | volume = 23 | issue = 19 | pages = 194103 | year = 2011 | bibcode = 2011JPCM...23s4103H }}</ref>

===Hexagonal packing of circles===

[[File:Circle packing (hexagonal).svg|thumb|right|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[[circle]]s, possibly of different sizes, on a surface, for instance the [[plane (geometry)|plane]] or a [[sphere]].

The [[N-sphere|counterparts of a circle]] in other dimensions can never be packed with complete efficiency in [[dimensionsdimension]]s larger than one (in a one-dimensional 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, [[Circle packing|hexagonal packing]], produces approximately 91% efficiency.<ref>{{Cite web | url=http://mathworld.wolfram.com/CirclePacking.html |title = Circle Packing}}</ref>

===Sphere packings in higher dimensions===

Line 27:

===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. [[Tetrahedron packing|Tetrahedra]] can achieve a packing of at least 85%. One of the best packings of regular [[dodecahedron|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]].

{| class="wikitable"

Line 36:

! Optimal density of a lattice packing

|-

| [[icosahedron]]

| 0.836357...<ref name="Betke">{{cite journal|last1=Betke|first1=Ulrich|last2=Henk|first2=Martin|doi=10.1016/S0925-7721(00)00007-9|doi-access=free|issue=3|journal=[[Computational Geometry (journal)|Computational Geometry]]|mr=1765181|pages=157–186|title=Densest lattice packings of 3-polytopes|volume=16|year=2000|arxiv=math/9909172|s2cid=12118403}}</ref>

|-

| dodecahedron

| (5 &thinsp;+ &thinsp;{{radic|5}})/8 = 0.904508...<ref name="Betke"/>

|-

| octahedron

Line 51:

=== Different cuboids into a cuboid ===

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===

The problem of finding the smallest ball such that <math>k</math> [[disjoint sets|disjoint]] open [[unit ballsball]]s may be packed inside it has a simple and complete answer in <math>n</math>-dimensional Euclidean space if <math> k \leq n+1</math>, 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 <math>k</math> pairwise [[Tangent#Tangent circles|tangent]] unit balls is available. Place the centers at the vertices <math>a_1, \dots, a_k</math> of a regular <math>(k-1)</math> 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 <math display="inline">\sqrt{2\big(1-\frac{1}{k} \big)}</math>. Moreover, any other point of the space necessarily has a larger distance from ''at least'' one of the <math> k</math> vertices. In terms of inclusions of balls, the <math> k</math> open unit balls centered at <math> a_1, \dots, a_k</math> are included in a ball of radius <math display="inline"> r_k := 1+\sqrt{2\big(1-\frac{1}{k}\big)}</math>, which is minimal for this configuration.

To show that this configuration is optimal, let <math> x_1, \dots, x_k</math> be the centers of <math> k</math> disjoint open unit balls contained in a ball of radius <math> r</math> centered at a point <math> x_0</math>. Consider the [[function (mathematics)|map]] from the finite set <math>\{x_1,\dots, x_k\}</math> into <math>\{a_1,\dots,a_k\}</math> taking <math> x_j</math> in the corresponding <math> a_j</math> for each <math> 1 \leq j \leq k</math>. Since for all <math> 1 \leq i < j \leq k</math>, <math> \|a_i-a_j\| = 2\leq\|x_i-x_j\|</math> this map is 1-[[Lipschitz continuity|Lipschitz]] and by the [[Kirszbraun theorem]] it extends to a 1-Lipschitz map that is globally defined; in particular, there exists a point <math> a_0</math> such that for all <math>1\leq j\leq k</math> one has <math>\|a_0-a_j\| \leq \|x_0-x_j\|</math>, so that also <math> r_k\leq1leq 1+\|a_0-a_j\|\leq 1+\|x_0-x_j\| \leq r</math>. This shows that there are <math> k</math> disjoint unit open balls in a ball of radius <math> r</math> [[if and only if]] <math> r \geq r_k</math>. Notice that in an infinite -dimensional Hilbert space this implies that there are infinitely many disjoint open unit balls inside a ball of radius <math> r</math> if and only if <math> r\geq 1+\sqrt{2}</math>. For instance, the unit balls centered at <math>\sqrt{2}e_j</math>, where <math>\{e_j\}_j</math> is an orthonormal basis, are disjoint and included in a ball of radius <math> 1 + \sqrt{2}</math> centered at the origin. Moreover, for <math> r < 1 + \sqrt{2}</math>, the maximum number of disjoint open unit balls inside a ball of radius <math>r</math> is <math display="inline">\big\lfloor \frac{2}{2-(r-1)^2}\big\rfloor</math>.

===Spheres in a cuboid===

Determine the number of [[sphere|spherical]] objects of given diameter ''d'' that can be packed into a [[cuboid]] of {{nowrap|size ''a'' × ''b'' × ''c''}}.

===Identical spheres in a cylinder===

Determine the minimum height ''h'' of a [[cylinder]] with given radius ''R'' that will pack ''n'' identical spheres of radius ''r'' (< ''R'').<ref>{{Cite journal | doi = 10.1111/j.1475-3995.2009.00733.x| title = Packing identical spheres into a cylinder| journal = International Transactions in Operational Research| volume = 17| pages = 51–70| year = 2010| last1 = Stoyan | first1 = Y. G. | last2 = Yaskov | first2 = G. N.}}</ref> For a small radius ''R'' the spheres arrange to ordered structures, called [[Columnar structure|columnar structures]].

===Polyhedra in spheres===

Determine the minimum radius ''R'' that will pack ''n'' identical, unit [[volume]] [[polyhedron|polyhedra]] of a given shape.<ref>{{Cite journal | doi = 10.1073/pnas.1524875113 | pmid = 26811458 | title = Clusters of Polyhedra in Spherical Confinement | journal = Proc. Natl. Acad. Sci. U.S.A. | volume = 113 | issue = 6 | pages = E669–E678 | year = 2016 | last1 = Teich | first1 = E.G. | last2 = van Anders | first2 = G. | last3 = Klotsa | first3 = D. | last4 = Dshemuchadse | first4 = J. | last5 = Glotzer | first5 = S.C.| pmc = 4760782 | bibcode = 2016PNAS..113E.669T | doi-access = free }}</ref>

==Packing in 2-dimensional containers==

Line 75:

* [[Circle packing in a circle|Packing circles in a '''circle''']] - 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''&nbsp;≤&nbsp;13, and&nbsp;''n''&nbsp;=&nbsp;19.

* [[Circle packing in a square|Packing circles in a '''square''']] - closely related to spreading points in a unit square with the objective of finding the greatest minimal separation, ''d''_''n'', between points. To convert between these two formulations of the problem, the square side for unit circles will be ''L''&nbsp;=&nbsp;2&nbsp;+&nbsp;2/''d''_''n''. [[File:15 circles in a square.svg|thumb|120px|right|The optimal packing of 15 circles in a square]]Optimal solutions have been proven for ''n''&nbsp;≤&nbsp;30.

* [[Circle packing in an isosceles right triangle|Packing circles in an '''isosceles right triangle''']] - good estimates are known for ''n'' < 300.

* [[Circle packing in an equilateral triangle|Packing circles in an '''equilateral triangle''']] - Optimal solutions are known for ''n'' < 13, and conjectures[[conjecture]]s are available for ''n''&nbsp;<&nbsp;28.<ref>{{Cite journal | last1 = Melissen | first1 = J. | title = Packing 16, 17 or 18 circles in an equilateral triangle | journal = Discrete Mathematics | volume = 145 | issue = 1–3 | pages = 333–342 | year = 1995 | doi = 10.1016/0012-365X(95)90139-C| url = https://research.utwente.nl/en/publications/packing-16-17-of-18-circles-in-an-equilateral-triangle(b2172f19-9654-4ff1-9af4-59da1b6bef3d).html }}</ref>

{{Anchor|Packing squares}}

Line 83:

You are given ''n'' [[unit square]]s and have to pack them into the smallest possible container, where the container type varies:

* [[Square packing in a square|Packing squares in a '''square''']]: Optimal solutions have been proven for ''n''&nbsp;=&nbsp;1–10, 14–16, 22–25, 33–36, 62–64, 79–81, 98–100, and any [[square number|square]] [[integer]]. The wasted space is asymptotically [[Big O notation|O]](''a''^7/11).

* [[Square packing in a circle|Packing squares in a '''circle''']]: Good solutions are known for ''n'' up to 35.[[Image:10 kvadratoj en kvadrato.svg|thumb|120px|right|The optimal packing of 10 squares in a square]]

===[[Rectangle packing|Packing of rectangles]]===

* '''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''&hairsp;&hairsp;) 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.

==Related fields==

In tiling or [[tessellation]] problems, there are to be no gaps, nor overlaps. Many of the puzzles of this type involve packing [[rectangles]] or [[polyominoespolyomino]]es into a larger rectangle or other square-like shape.

There are significant theorems[[theorem]]s on tiling rectangles (and cuboids) in rectangles (cuboids) with no gaps or overlaps:

:An ''a'' &times;× ''b'' rectangle can be packed with 1 &times;× ''n'' strips iffif and only if ''n'' divides ''a'' or ''n'' divides ''b''.<ref name="Gems2">{{cite book | title = Mathematical Gems II | last1 = Honsberger | first1 = Ross | year = 1976 | publisher = [[The Mathematical Association of America]] | isbn = 0-88385-302-7 | page = 67 }}</ref><ref name="Klarner">{{cite journal | title = Uniformly coloured stained glass windows | journal = Proceedings of the London Mathematical Society |series = 3 | volume = 23 | issue = 4 | pages = 613–628 | last1 = Klarner | first1 = D.A. | last2 = Hautus | first2 = M.L.J | author-link1 = David A. Klarner | year = 1971 | doi = 10.1112/plms/s3-23.4.613 }}</ref>

:[[de Bruijn's theorem]]: A box can be packed with a [[harmonic brick]] ''a'' &times;× ''a b'' &times;× ''a b c'' if the box has dimensions ''a p'' &times;× ''a b q'' &times;× ''a b c r'' for some [[natural number]]s ''p'', ''q'', ''r'' (i.e., the box is a multiple of the brick.)<ref name="Gems2"/>

The study of [[polyomino]] tilings largely concerns two classes of problems: to tile a rectangle with [[congruence|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 [[pentomino]]es into rectangles sized 3×20, 4×15, 5×12 or 6×10.

Line 105:

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.<ref>C.Michael Hogan. 2010. [http://www.eoearth.org/article/Abiotic_factor?topic=49461 ''Abiotic factor''. Encyclopedia of Earth. eds Emily Monosson and C. Cleveland. National Council for Science and the Environment]. Washington DC</ref>

The problem of deciding whether a given set of polygons[[polygon]]s can fit in a given square container has been shown to be complete for the [[existential theory of the reals]].<ref>{{citation

| last1 = Abrahamsen | first1 = Mikkel

| last2 = Miltzow | first2 = Tillmann