Finite sphere packing

File:Sausage_packing.svg

In general, a packing refers to any arrangement of a set of spatially-connected, possibly differently-sized or differently-shaped objects in space such that none of them overlap. In the case of the finite sphere packing problem, these objects are restricted to equally-sized spheres. Such a packing of spheres determines a specific volume known as the convex hull of the packing, defined as the smallest convex set that includes all the spheres.

There are many possible ways to arrange spheres, which can be classified into three basic groups: sausage, pizza, and cluster packing.{{Cite journal|title=Spheres and Sausages, crystals and catastrophes- and a joint packing theory |date=1998 |volume=20 |pages=16–21 |doi=10.1007/bf03024394 |issn=0343-6993 |issue=1|last1=Wills |first1=J. M. |journal=The Mathematical Intelligencer |s2cid=122751296 }}

File:Kugelwurst.svg|Sausage packing

File:SetUpofTriangleForStandardPool.jpg|Pizza packing

File:Kugelcluster.svg|Cluster packing

An arrangement in which the midpoint of all the spheres lie on a single straight line is called a sausage packing, as the convex hull has a sausage-like shape. An approximate example in real life is the packing of tennis balls in a tube, though the ends must be rounded for the tube to coincide with the actual convex hull.

If all the midpoints lie on a plane, the packing is a pizza packing. Approximate real-life examples of this kind of packing include billiard balls being packed in a triangle as they are set up. This holds for packings in three-dimensional Euclidean space.

If the midpoints of the spheres are arranged throughout 3D space, the packing is termed a cluster packing. Real-life approximations include fruit being packed in multiple layers in a box.

By the given definitions, any sausage packing is technically also a pizza packing, and any pizza packing is technically also a cluster packing. In the more general case of $d$ dimensions, "sausages" refer to one-dimensional arrangements, "clusters" to $d$-dimensional arrangements, and "pizzas" to those with an in-between number of dimensions.

One or two spheres always make a sausage. With three, a pizza packing (that is not also a sausage) becomes possible, and with four or more, clusters (that are not also pizzas) become possible.

The empty space between spheres varies depending on the type of packing. The amount of empty space is measured in the packing density, which is defined as the ratio of the volume of the spheres to the volume of the total convex hull. The higher the packing density, the less empty space there is in the packing and thus the smaller the volume of the hull (in comparison to other packings with the same number and size of spheres).

To pack the spheres efficiently, it might be asked which packing has the highest possible density. It is easy to see that such a packing should have the property that the spheres lie next to each other, that is, each sphere should touch another on the surface. A more exact phrasing is to form a graph which assigns a vertex for each sphere and connects vertices with edges whenever the corresponding spheres if their surfaces touch. Then the highest-density packing must satisfy the property that the corresponding graph is connected.

With three or four spheres, the sausage packing is optimal. It is believed that this holds true for any $n$ up to $55$ along with $n=57,\; 58,\; 63,\; 64$.{{Cite book|last=Leppmeier |first=Max |url=http://link.springer.com/10.1007/978-3-322-80299-6 |title=Kugelpackungen von Kepler bis heute |date=1997 |publisher=Vieweg+Teubner Verlag |isbn=978-3-528-06792-2 |location=Wiesbaden |language=de |doi=10.1007/978-3-322-80299-6}} For $n=56,\; 59,\; 60,\; 61,\; 62$ and $n\; \backslash geq\; 65$, a cluster packing exists that is more efficient than the sausage packing, as shown in 1992 by Jörg Wills and Pier Mario Gandini.{{Cite journal|last1=Gandini |first1=P. M. |last2=Wills |first2=J. M. |date=1992 |title=On finite sphere-packings |url=http://mathematica-pannonica.ttk.pte.hu/articles/mp03-1/mp03-1-019-029.pdf |journal=Mathematica Pannonica |volume=3 |issue=1 |pages=19–29}} It remains unknown what these most efficient cluster packings look like. For example, in the case $n\; =\; 56$, it is known that the optimal packing is not a tetrahedral packing like the classical packing of cannon balls, but is likely some kind of octahedral shape.

The sudden transition in optimal packing shape is jokingly known by some mathematicians as the sausage catastrophe{{cite journal

| last = Wills | first = J. M.

| doi = 10.1007/BF01849026

| issue = 3-4

| journal = Periodica Mathematica Hungarica

| mr = 1553625

| pages = 309–314

| title = Research problems

| volume = 14

| year = 1983}}{{cite encyclopedia|last1=Gritzmann |first1=Peter |title=Finite Packing and Covering |date=1993 |url=https://linkinghub.elsevier.com/retrieve/pii/B9780444895974500081 |encyclopedia=Handbook of Convex Geometry |pages=861–897 |publisher=Elsevier |language=en |doi=10.1016/b978-0-444-89597-4.50008-1 |isbn=978-0-444-89597-4 |access-date=2022-04-17 |last2=Wills |first2=Jörg M.}} The designation catastrophe comes from the fact that the optimal packing shape suddenly shifts from the orderly sausage packing to the relatively unordered cluster packing and vice versa as one goes from one number to another, without a satisfying explanation as to why this happens. Even so, the transition in three dimensions is relatively tame; in four dimensions, the sudden transition is conjectured to happen around 377,000 spheres.

For dimensions $d\; \backslash leq\; 10$, the optimal packing is always either a sausage or a cluster, and never a pizza. It is an open problem whether this holds true for all dimensions. This result only concerns spheres and not other convex bodies; in fact Gritzmann and Arhelger observed that for any dimension $d\; \backslash geq\; 3$ there exists a convex shape for which the closest packing is a pizza.

In the following section it is shown that for 455 spheres the sausage packing is non-optimal, and that there instead exists a special cluster packing that occupies a smaller volume.

The volume of a convex hull of a sausage packing with $n$ spheres of radius $r$ is calculable with elementary geometry. The middle part of the hull is a cylinder with length $h\; =\; 2r\; \backslash cdot\; (n-1)$ while the caps at the end are half-spheres with radius $r$. The total volume $V\_W$ is therefore given by.

: $\backslash begin\{align\}$

V_W &= V_\text{cylinder} + 2 \cdot V_\text{half-sphere}\\

&= V_\text{cylinder} + V_\text{sphere}\\

&= \pi h r^2 + \frac{4}{3}\pi r^3\\

&= \pi 2r \cdot (n-1) \cdot r^2 + \frac{4}{3}\pi r^3\\

&= 2 \cdot \left( n - \frac{1}{3}\right) \pi r^3

\end{align}

Similarly, it is possible to find the volume of the convex hull of a tetrahedral packing, in which the spheres are arranged so that they form a tetrahedral shape, which only leads to completely filled tetrahedra for specific numbers of spheres. If there are $x$ spheres along one edge of the tetrahedron, the total number of spheres $n$ is given by

: $n\; =\; \backslash sum\_\{i=1\}^x\backslash sum\_\{j=1\}^i\; j\; =\; \backslash sum\_\{i=1\}^x\; \backslash frac\{i\backslash cdot(i+1)\}\{2\}\; =\; \backslash frac\{x\backslash cdot(x+1)\backslash cdot(x+2)\}\{6\}$.

Now the inradius $r$ of a tetrahedral with side length $a$ is

: $r\; =\; \backslash frac\{\backslash sqrt\{6\}\}\{12\}\; \backslash cdot\; a$.

From this we have

: $a\; =\; 2\backslash sqrt\{6\}\; \backslash cdot\; r$.

The volume $V\_T$ of the tetrahedron is then given by the formula

: $V\_T\; =\; \backslash frac\{\backslash sqrt\{2\}\}\{12\}\; \backslash cdot\; a^3\; =\; \backslash sqrt\{192\}\; \backslash cdot\; r^3$

In the case of many spheres being arranged inside a tetrahedron, the length of an edge $a$ increases by twice the radius of a sphere for each new layer, meaning that for $x$ layers the side length becomes

: $a\; =\; 2\; \backslash cdot\; \backslash left(\; x\; -\; 1\; +\; \backslash sqrt\{6\}\; \backslash right)\; \backslash cdot\; r$.

Substituting this value into the volume formula for the tetrahedron, we know that the volume $V$ of the convex hull must be smaller than the tetrahedron itself, so that

: .

Taking the number of spheres in a tetrahedron of $n$ layers and substituting into the earlier expression to get the volume $V\_\backslash text\{W\}$ of the convex hull of a sausage packing with the same number of spheres, we have

: $V\_\backslash text\{W\}\; =\; \backslash frac\{x\backslash cdot(x+1)\backslash cdot(x+2)-2\}\{3\}\; \backslash cdot\; \backslash pi\; r^3$.

For $x\; =\; 13$, which translates to $n\; =\; 455$ spheres the coefficient in front of $r^3$ is about 2845 for the tetrahedral packing and 2856 for the sausage packing, which implies that for this number of spheres the tetrahedron is more closely packed.

It is also possible with some more effort to derive the exact formula for the volume of the tetrahedral convex hull $V$, which would involve subtracting the excess volume at the corners and edges of the tetrahedron. This allows the sausage packing to be proved non-optimal for smaller values of $x$ and therefore $n$.

The term sausage comes from the mathematician László Fejes Tóth, who posited the sausage conjecture in 1975,{{Cite journal|last1=Hajnal |first1=A. |last2=Tóth |first2=L. Fejes |date=1975 |title=Research problems |url=http://link.springer.com/10.1007/BF02018822 |journal=Periodica Mathematica Hungarica |language=en |volume=6 |issue=2 |pages=197–199 |doi=10.1007/BF02018822 |s2cid=189833485 |issn=0031-5303}} which concerns a generalized version of the problem to spheres, convex hulls, and volume in higher dimensions. A generalized sphere in $d$ dimensions is a $d$-dimensional body in which every boundary point lies equally far away from the midpoint. Fejes Tóth's sausage conjecture then states that from $d=5$ upwards it is always optimal to arrange the spheres along a straight line. That is, the sausage catastrophe no longer occurs once we go above 4 dimensions. The overall conjecture remains open. The best results so far are those of Ulrich Betke and Martin Henk,{{Cite journal|last1=Betke |first1=U. |last2=Henk |first2=M. |date=1998 |title=Finite Packings of Spheres |journal=Discrete & Computational Geometry |language=en |volume=19 |issue=2 |pages=197–227 |doi=10.1007/PL00009341 |issn=0179-5376|doi-access=free }} who proved the conjecture for dimensions 42 and above.

While it may be proved that the sausage packing is not optimal for 56 spheres, and that there must be some other packing that is optimal, it is not known what the optimal packing looks like. It is difficult to find the optimal packing as there is no "simple" formula for the volume of an arbitrarily shaped cluster. Optimality (and non-optimality) is shown through appropriate estimates of the volume, using methods from convex geometry, such as the Brunn-Minkowski inequality, mixed Minkowski volumes and Steiner's formula. A crucial step towards a unified theory of both finite and infinite (lattice and non-lattice) sphere packings was the introduction of parametric densities by Jörg Wills in 1992. The parametric density takes into account the influence of the edges of the packing.{{Cite journal|last=Wills |first=Jörg M. |date=1995-01-01 |title=Kugelpackungen- Altes und Neues |url=https://www.degruyter.com/document/doi/10.1515/dmvm-1995-0407/html |journal=Mitteilungen der Deutschen Mathematiker-Vereinigung |volume=3 |issue=4 |doi=10.1515/dmvm-1995-0407 |s2cid=179051027 |issn=0942-5977|doi-access=free }}

The definition of density used earlier concerns the volume of the convex hull of the spheres (or convex bodies) $K$:

: $\backslash delta\; (K,\; C\_n)\; =\backslash frac\; \{n\; V(K)\}\{V\; (C\_n\; +K)\}$

where $C\_n$ is the convex hull of the $n$ midpoints $c\_i$ of the spheres $K\_i$ (instead of the sphere, we can also take an arbitrary convex body for $K$). For a linear arrangement (sausage), the convex hull is a line segment through all the midpoints of the spheres. The plus sign in the formula refers to Minkowski addition of sets, so that $V\; (C\_n\; +\; K)$ refers to the volume of the convex hull of the spheres.

This definition works in two dimensions, where Laszlo Fejes-Toth, Claude Rogers and others used it to formulate a unified theory of finite and infinite packings. In three dimensions, Wills gives a simple argument that such a unified theory is not possible based on this definition: The densest finite arrangement of coins in three dimensions is the sausage with $\backslash delta\; =1$. However, the optimal infinite arrangement is a hexagonal arrangement with $\backslash delta\; \backslash approx\; 0.9$, so the infinite value cannot be obtained as a limit of finite values. To solve this issue, Wills introduces a modification to the definition by adding a positive parameter $\backslash rho$:

: $\backslash delta\; (K,\; C\_n)\; =\backslash frac\; \{n\; V(K)\}\{V\; (C\_n\; +\; \backslash rho\; K)\}$

$\backslash rho$ allows the influence of the edges to be considered (giving the convex hull a certain thickness). This is then combined with methods from the theory of mixed volumes and geometry of numbers by Hermann Minkowski.

For each dimension $d\; \backslash geq\; 2$ there are parameter values $\backslash rho\_s\; (d)$ and $\backslash rho\_c\; (d)$ such that for $\backslash rho\; \backslash leq\; \backslash rho\_s\; (d)$ the sausage is the densenst packing (for all integers $n$), while for $\backslash rho\; \backslash geq\; \backslash rho\_c\; (d)$ and suffiricently large $n$ the cluster is densest. These parameters are dimension-specific. In two dimensions, $\backslash rho\_c\; (2)=\backslash rho\_s\; (2)=\; \backslash frac\; \{\backslash sqrt\; \{3\}\}\{2\}$ so that there is a transition from sausages to clusters (sausage catastrophe).

There holds an inequality:

: $\backslash frac\; \{V\; (B^d)\}\{2\; V\; (B^\{d-1\})\}\; \{\backslash rho\_c\; (d)\}^\{1-d\}\; \backslash leq\; \backslash delta\; (B^d)\; \backslash leq\; \backslash frac\; \{V\; (B^d)\}\{2\; V\; (B^\{d-1\})\}\; \{\backslash rho\_s\; (d)\}^\{1-d\}$

where the volume of the unit ball $B^d$ in $d$ dimensions is $V\; (B^d)$. For $d\; =\; 2$, we have $\backslash rho\_s\; (d)\; =\backslash rho\_c\; (d)$ and it is predicted that this holds for all dimensions, in which case the value of $\backslash rho\_c\; (d)$ can be found from that of $\backslash delta\; (B^d)$.

{{Packing problems}}

Category:Euclidean solid geometry