Packing problems

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.

In a bin packing problem, people are given:

  • 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.[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.

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.

Solid Optimal density of a lattice packing
icosahedron 0.836357...[10]
dodecahedron (5 + 5)/8 = 0.904508...[10]
octahedron 18/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

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

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

  • 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 ) 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 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. ^ a b 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. ^ a b 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. ^ a b 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.

References

External links

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

Read other articles:

Kampanye PhiladelphiaBagian dari Perang Revolusi Amerika SerikatPatung Anthony Wayne di Valley ForgeTanggal1777–1778LokasiNew Jersey, Maryland, Delaware, dan PennsylvaniaHasil Pendudukan Britania yang berakhir dengan evakuasi PhiladelphiaPihak terlibat  United States  Britania Raya Hesse-KasselAnsbach-BayreuthTokoh dan pemimpin George WashingtonNathanael Greene William HoweHenry ClintonKekuatan Sekitar 20.000+ Sekitar 16.000+lbsKampanyePhiladelphia 1777–1778 Bound Brook Short Hills…

Kia K8기아 케이에잇Kia K8 G1.6 T-GDi Hybrid Signature (Snow White Pearl) (Korea)InformasiProdusenKiaMasa produksiApril 2021–sekarangModel untuk tahun2022-sekarangPerakitanKorea Selatan: Hwasung, Gyeonggi (Kia Hwasung Plant)Uzbekistan: Jizzakh (ADM-Jizzakh)PerancangKarim HabibBodi & rangkaKelasMobil EksekutifBentuk kerangkaSedan 4-pintuTata letak Mesin depan, penggerak roda depan Mesin depan, penggerak semua roda Mobil terkaitHyundai AzeraPenyalur dayaMesinBensin SmartStream…

Chris Kirkland Informasi pribadiNama lengkap Christopher Edmund KirklandTanggal lahir 2 Mei 1981 (umur 42)Tempat lahir Barwell, Leicestershire, InggrisTinggi 1,91 m (6 ft 3 in)[1]Posisi bermain Penjaga gawangInformasi klubKlub saat ini Sheffield WednesdayNomor –Karier senior*Tahun Tim Tampil (Gol)1998–2001 Coventry City 24 (0)2001–2006 Liverpool 25 (0)2005–2006 → West Bromwich Albion (pinjaman) 10 (0)2006 → Wigan Athletic (pinjaman) 1 (0)2006–2012 Wigan …

Формула условного крещения в Требнике Петра Могилы Усло́вное креще́ние или креще́ние под конди́цией (лат. baptismum conditionalis, baptismum sub conditione) — крещение в католицизме[1] над человеком, о предыдущем крещении которого есть сомнение — было ли оно совершено или нет; при э…

Artikel ini membutuhkan rujukan tambahan agar kualitasnya dapat dipastikan. Mohon bantu kami mengembangkan artikel ini dengan cara menambahkan rujukan ke sumber tepercaya. Pernyataan tak bersumber bisa saja dipertentangkan dan dihapus.Cari sumber: Anis siberia – berita · surat kabar · buku · cendekiawan · JSTOR (April 2021) Anis siberia Status konservasi Risiko Rendah (IUCN 3.1)[1] Klasifikasi ilmiah Kerajaan: Animalia Filum: Chordata Kelas: …

Season of television series Channel 4's Comedy GalaSeason 4StarringJo BrandBill BaileyJohn BishopKevin BishopKevin BridgesAlan CarrJames CordenJack DeeLee EvansNoel FieldingRuth JonesRich HallShappi KhorsandiPatrick KieltySean LockStompJason ManfordMichael McIntyreDavid MitchellAndy ParsonsMark WatsonRobert WebbJack WhitehallNo. of episodes1ReleaseOriginal networkChannel 4Original release5 April 2010 (2010-04-05)Season chronology← Previous— Next →2011 Channel 4…

Kue Putri Selat Putri Selat adalah kue tradisional khas masyarakat Banjar di Kalimantan Selatan. Kue ini terdiri dari 3 lapisan dengan masing-masing lapisan memiliki cita rasanya sendiri. Pada umumnya lapisan bawah terdiri dari bahan dasar adonan tepung dan kelapa parut, lapisan tengah terbuat dari adonan gula merah dan lapisan atas berupa berbahan dasar daun suji dan berwarna hijau. Sehingga memberikan cita rasa manis, gurih dan legit dalam satu potongan.[1] Kue ini biasanya dijumpai di…

Pour les articles homonymes, voir Fitz-James (homonymie). Charles de Fitz-James Titre 4e duc de Fitz-James et pair de France (1736-1769) Prédécesseur François de Fitz-James Successeur Jacques-Charles de Fitz-James Allégeance Royaume de France Grade militaire Maréchal de France Commandement Commandant de la province de Languedoc Gouvernement militaire Gouverneur du Limousin Conflits Guerre de Succession de PologneGuerre de Succession d'AutricheGuerre de Sept Ans Distinctions Maison de Fitz-J…

Axel Gustafsson Oxenstierna af Södermöre Retrato de Axel Oxenstierna en el Museo Nacional de EstocolmoInformación personalNacimiento Fånö, UpplandFamiliaPadre Gustaf Gabrielsson OxenstiernaMadre Barbro Axelsdotter BielkeCónyuge Anna Åkesdotter Bååt Firma [editar datos en Wikidata] Axel Gustafsson Oxenstierna af Södermöre (en sueco: ˈʊksɛnˌɧæːɳa; Fånö, 16 de junio de 1583-Estocolmo, 28 de agosto de 1654) fue un noble y político sueco, conde de Södermöre, miembro …

Pour les articles homonymes, voir Hardware (homonymie). Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (septembre 2013). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ». En …

Keuskupan Agung Buenos AiresArchidioecesis BonaerensisArquidiócesis de Buenos AiresKatolik Katedral Metropolitan Buenos AiresLokasiNegara ArgentinaWilayahBuenos AiresProvinsi gerejawiBuenos AiresStatistikLuas78 sq mi (200 km2)Populasi- Total- Katolik(per 2012)2.917.0002,671,000 (91.6%)Paroki186Imam471InformasiDenominasiKatolik RomaRitusRitus RomaPendirian6 April 1620KatedralKatedral Metropolitan Buenos AiresPelindungNuestra Señora del Buen AireKepemimpin…

В Википедии есть статьи о других людях с фамилией Вишневецкая. Раина Могилянка-Вишневецкая Рождение 1589Sucevița[d], Сучава, Румыния Смерть 1619Вишневец, Кременецкий повят[d], Волынское воеводство, Малопольская провинция, Корона Королевства Польского, Речь Посполитая Род Могилы …

2012 military operation of the Syrian civil war This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Talbiseh bakery massacre – news · newspapers · books · scholar · JSTOR (October 2015) The neutrality of this article is disputed. Relevant discussion may be found on the talk page. Please do not remove this…

Pour les articles homonymes, voir GCD. Cet article est une ébauche concernant les comics. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Logo du Grand Comics Database. La Grand Comics Database (GCD ; en français : « Grande base de données de la bande dessinée ») est une base de données en ligne visant à répertorier l'ensemble des bandes dessinées publiées dans le monde sous divers for…

Dutch truck racer In this Dutch name, the surname is de Rooy, not Rooy. Gerard de RooyGerard de Rooy in 2013NationalityDutchBorn (1980-06-21) 21 June 1980 (age 43)Eindhoven, NetherlandsRelated toJan de Rooy (father) Gerard de Rooy (born 21 June 1980 in Eindhoven, Netherlands) is a Dutch truck racer, best known for participating in the Dakar Rally. In the 2009 edition he won three stages. He won the truck category race in 2012 and 2016. He is the son of successful rally raid driver Jan de Ro…

Halaman ini berisi artikel tentang pesepak bola profesional. Untuk orang lain bernama Francis Lee, lihat Francis Lee. Francis LeeCBE Informasi pribadiNama lengkap Francis Henry LeeTanggal lahir (1944-04-29)29 April 1944Tempat lahir Westhoughton, Lancashire, InggrisTanggal meninggal 2 Oktober 2023(2023-10-02) (umur 79)Posisi bermain PenyerangKarier senior*Tahun Tim Tampil (Gol)1959–1967 Bolton Wanderers 189 (92)1967–1974 Manchester City 249 (112)1974–1976 Derby County 62 (24)Total 500 …

† Стеллерова корова Муляж стеллеровой коровы в Лондонском музее естествознания Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:Челюстноро…

Videotelefoni terdiri dari teknologi untuk penerimaan dan transmisi sinyal audiovideo oleh pengguna di lokasi yang berbeda, untuk komunikasi antara orang-orang secara waktu nyata. Pada teknologi videotelefoni juga termasuk ponsel gambar yang akan bertukar gambar diam antara unit setiap beberapa detik melalui saluran telepon POTS-tipe konvensional, pada dasarnya sama dengan TV scan sistem lambat. Saat ini penggunaan videotelefoni telah membuat terobosan signifikan dalam pemerintahan, kesehatan, p…

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Cricket in Canada – news · newspapers · books · scholar · JSTOR (October 2016) (Learn how and when to remove this message) Cricket in CanadaCricket match in progress in Vancouver's Stanley ParkCountryCanadaGoverning bodyCricket CanadaNational team(s) Men's nationa…

Державний комітет телебачення і радіомовлення України (Держкомтелерадіо) Приміщення комітетуЗагальна інформаціяКраїна  УкраїнаДата створення 2003Керівне відомство Кабінет Міністрів УкраїниРічний бюджет 1 964 898 500 ₴[1]Голова Олег НаливайкоПідвідомчі орг…

Kembali kehalaman sebelumnya