Packing problems: Difference between revisions

Revision as of 20:27, 17 September 2023

Revision as of 23:31, 26 September 2023

Line 11:

* 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|authorsauthor= Lodi, A., |author2=Martello, S., |author3=Monaci, M. |title = Two-dimensional packing problems: A survey| journal = European Journal of Operational Research|year = 2002|publisher = Elsevier|doi=10.1016/s0377-2217(02)00123-6|volume=141|issue = 2|pages=241–252}}</ref> 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 [[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 | pagespage = 194103 | year = 2011 | bibcode = 2011JPCM...23s4103H | s2cid = 25505460 }}</ref>

===Hexagonal packing of circles===