Packing problems: Difference between revisions

Content deleted Content added
m doi-access=free + some accents fixed
\scriptstyle too small
Tags: Mobile edit Mobile web edit Advanced mobile edit
Line 54:
 
===Spheres into a Euclidean ball===
The problem of finding the smallest ball such that <math>k</math> disjoint open unit balls may be packed inside it has a simple and complete answer in <math>n</math>-dimensional Euclidean space if <math>\scriptstyle 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 <math>k</math> pairwise tangent unit balls is available. Place the centers at the vertices <math>a_1,.. \dots, a_k</math> of a regular <math>\scriptstyle(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">\scriptstyle\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 <math>\scriptstyle k</math> vertices. In terms of inclusions of balls, the <math>\scriptstyle k</math> open unit balls centered at <math>\scriptstyle a_1,.. \dots, a_k</math> are included in a ball of radius <math display="inline">\scriptstyle 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>\scriptstyle x_1,... \dots, x_k</math> be the centers of <math>\scriptstyle k</math> disjoint open unit balls contained in a ball of radius <math>\scriptstyle r</math> centered at a point <math>\scriptstyle x_0</math>. Consider the map from the finite set <math>\scriptstyle\{x_1,..\dots, x_k\}</math> into <math>\scriptstyle\{a_1,..\dots,a_k\}</math> taking <math>\scriptstyle x_j</math> in the corresponding <math>\scriptstyle a_j</math> for each <math>\scriptstyle 1 \leq j \leq k</math>. Since for all <math>\scriptstyle 1\leq i < j \leq k</math>, <math>\scriptstyle \|a_i-a_j\|=2\leq\|x_i-x_j\|</math> 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 <math>\scriptstyle a_0</math> such that for all <math>\scriptstyle11\leq j\leq k</math> one has <math>\scriptstyle\|a_0-a_j\| \leq \|x_0-x_j\|</math>, so that also <math>\scriptstyle r_k\leq1+\|a_0-a_j\|\leq 1+\|x_0-x_j\| \leq r</math>. This shows that there are <math>\scriptstyle k</math> disjoint unit open balls in a ball of radius <math>\scriptstyle r</math> if and only if <math>\scriptstyle 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 <math>\scriptstyle r</math> if and only if <math>\scriptstyle r\geq 1+\sqrt{2}</math>. For instance, the unit balls centered at <math>\scriptstyle\sqrt{2}e_j</math>, where <math>\scriptstyle\{e_j\}_j</math> is an orthonormal basis, are disjoint and included in a ball of radius <math>\scriptstyle 1 + \sqrt{2}</math> centered at the origin. Moreover, for <math>\scriptstyle r < 1 + \sqrt{2}</math>, the maximum number of disjoint open unit balls inside a ball of radius r is <math display="inline">\scriptstyle\big\lfloor \frac{2}{2-(r-1)^2}\big\rfloor</math>.
 
===Spheres in a cuboid===