Packing problems: Difference between revisions

Revision as of 06:23, 7 December 2023

Latest revision as of 13:44, 19 July 2025

(13 intermediate revisions by 12 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]], youpeople 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.

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 youpeople 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 41:

|-

| dodecahedron

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

|-

| 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. PlacePeople 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 {{mvar|k}} vertices. In terms of inclusions of balls, the {{mvar|k}} 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 {{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="inlineblock">\bigleft\lfloor \frac{2}{2-(r-1)^2}\bigright\rfloor.</math>.

===Spheres in a cuboid===

{{See also|Sphere packing in a cube}}

DeterminePeople determine the number of spherical objects of given diameter {{mvar|d}} that can be packed into a cuboid of size <math>a \times b \times c</math>.

===Identical spheres in a cylinder===

{{main article|Sphere packing in a cylinder}}

DeterminePeople determine the minimum height {{mvar|h}} of a [[cylinder]] with given radius {{mvar|R}} that will pack {{mvar|n}} identical spheres of radius {{math|''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 {{mvar|R}} the spheres arrange to ordered structures, called [[Columnar structure|columnar structures]].

===Polyhedra in spheres===

DeterminePeople determine the minimum radius {{mvar|R}} that will pack {{mvar|n}} identical, unit [[volume]] [[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==

[[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. See the linked pages for more information.

=== Packing of circles ===

{{main article|Circle packing}}

YouPeople are given {{mvar|n}} [[unit circle]]s, and have to pack them in the smallest possible container. Several kinds of containers have been studied:

* [[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'' ≤ 1314}}, and {{math|1=''n'' = 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, {{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'' <≤ 1315}}, and [[conjecture]]s are available for {{math|''n'' <≤ 2834}}.<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 | doi-access = free }}</ref>

{{Anchor|Packing squares}}

Line 90:

{{main|Square packing}}

YouPeople 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|73/115}})}}.

* [[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]]