Content deleted Content added
Niklas Bäck (talk | contribs) Changed numbers according to the main article |
|||
| (32 intermediate revisions by 27 users not shown) | |||
Line 7:
'''Packing problems''' are a class of [[optimization problem]]s in [[mathematics]] that involve attempting to pack objects together into containers. The goal is to either pack a single container as [[Packing density|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]],
* 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.<ref>{{cite journal|
==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 solid]]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 [[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 |
===Hexagonal packing of circles===
Line 20:
These problems are mathematically distinct from the ideas in the [[circle packing theorem]]. The related [[circle packing]] problem deals with packing [[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 [[dimension]]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
===Sphere packings in higher dimensions===
Line 41:
|-
| dodecahedron
| {{math|1=(5
|-
| octahedron
Line 50:
==Packing in 3-dimensional containers==
[[File:9L cube puzzle solution.svg|thumb|right|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.
Line 56:
===Spheres into a Euclidean ball===
{{main article|Sphere packing in a sphere}}
The problem of finding the smallest ball such that {{mvar|k}} [[disjoint sets|disjoint]] open [[unit ball]]s may be packed inside it has a simple and complete answer in {{mvar|n}}-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 {{mvar|k}} pairwise [[Tangent#Tangent circles|tangent]] unit balls is available.
To show that this configuration is optimal, let <math>x_1, \dots, x_k</math> be the centers of {{mvar|k}} disjoint open unit balls contained in a ball of radius {{mvar|r}} 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\leq 1+\|a_0-a_j\|\leq 1+\|x_0-x_j\| \leq r</math>. This shows that there are {{mvar|k}} disjoint unit open balls in a ball of radius {{mvar|r}} [[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 {{mvar|r}} 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 {{mvar|r}} is <math display="
===Spheres in a cuboid===
{{See also|Sphere packing in a cube}}
===Identical spheres in a cylinder===
{{main article|Sphere packing in a cylinder}}
===Polyhedra in spheres===
==Packing in 2-dimensional containers==
[[Image:Disk pack10.svg|thumb|120px|right|The optimal packing of 10 circles in a circle]]Many variants of 2-dimensional packing problems have been studied
=== Packing of circles ===
{{main article|Circle packing}}
* [[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, {{mvar|d{{sub|n}}}}, between points. Optimal solutions have been proven for {{math|''n'' ≤
* [[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, {{mvar|d{{sub|n}}}}, between points. To convert between these two formulations of the problem, the square side for unit circles will be <math>L = 2 + 2/d_n</math>. [[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 {{math|''n'' ≤ 30}}.
* [[Circle packing in a rectangle|Packing circles in a '''rectangle''']]
* [[Circle packing in an isosceles right triangle|Packing circles in an '''isosceles right triangle''']] - good estimates are known for {{math|''n'' < 300}}.
* [[Circle packing in an equilateral triangle|Packing circles in an '''equilateral triangle''']] - Optimal solutions are known for {{math|''n''
{{Anchor|Packing squares}}
=== Packing of squares ===
{{main|Square packing}}
You are given {{mvar|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 {{mvar|n}} from 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 {{math|[[Big O notation|O]](''a''{{sup|7/11}})}}.▼
▲* [[Square packing in a square|Packing squares in a '''square''']]: Optimal solutions have been proven for {{mvar|n}} from 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 {{math|[[Big O notation|O]](''a''{{sup|
* [[Square packing in a circle|Packing squares in a '''circle''']]: Good solutions are known for {{math|''n'' ≤ 35}}.[[Image:10 kvadratoj en kvadrato.svg|thumb|120px|right|The optimal packing of 10 squares in a square]]
Line 121 ⟶ 124:
==See also==
* [[Set packing]]▼
* [[Bin packing problem]]
* [[Close-packing of equal spheres]]▼
* [[Slothouber–Graatsma puzzle]]▼
* [[Conway puzzle]]
* [[Tetris]]▼
* [[Covering problem]]
* [[Knapsack problem]]▼
* [[Tetrahedron packing]]▼
* [[Ellipsoid packing]]▼
* [[Cutting stock problem]]
▲* [[Ellipsoid packing]]
* [[Kissing number problem]]
▲* [[Knapsack problem]]
▲* [[Close-packing of equal spheres]]
* [[Random close pack]]
▲* [[Set packing]]
▲* [[Slothouber–Graatsma puzzle]]
* [[Strip packing problem]]
▲* [[Tetrahedron packing]]
▲* [[Tetris]]
==Notes==
Line 146 ⟶ 149:
{{Commons category}}
* [https://web.archive.org/web/20190303205438/http://pdfs.semanticscholar.org/bb99/86af2f26f7726fcef1bc684eac8239c9b853.pdf Optimizing Three-Dimensional Bin Packing]
Many puzzle books as well as mathematical journals contain articles on packing problems.
* [http://mathworld.wolfram.com/Packing.html Links to various MathWorld articles on packing]
| |||