Content deleted Content added
{{mergefrom|Nesting algorithm}} Tags: Reverted 2017 wikitext editor |
Niklas Bäck (talk | contribs) Changed numbers according to the main article |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 1:
{{short description|Problems which attempt to find the most efficient way to pack objects into containers}}
{{about|geometric packing problems|numerical packing problems|Knapsack problem}}
[[File:Seissand.png|thumb|[[Sphere]]s or [[circle]]s packed loosely (top) and more densely (bottom)]]
Line 42 ⟶ 41:
|-
| dodecahedron
| {{math|1=(5
|-
| octahedron
Line 59 ⟶ 58:
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. People 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="
===Spheres in a cuboid===
Line 80 ⟶ 79:
People 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'' ≤
* [[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}}
| |||