Finite Packing Theory

The mathematical theory of finite packing of spheres deals with the question of how a finite number of spheres of the same size can be packed in the most space-saving way possible. Finite packing of spheres has only been examined more mathematically in the last few decades. László Fejes Tóth laid important foundations for this.

The problem of closest packing for infinite packing of spheres , however, has a much longer tradition . The most famous conjecture is the Kepler conjecture . Atoms in crystal structures can be viewed in simplified form as packings of spheres and, due to their high number, they can be viewed as a good approximation of infinite packings of spheres.

When it comes to problems, a distinction is made between packs in a given convex body (container, bin pack, see also container problem ) and free packs. In the following (with the exception of the last section), the problem of free finite packing is mainly treated.

Packing and convex hull

Convex hull, colored blue

In a general and clear way, any arrangement of a set of spatially connected objects in space, possibly of different sizes and shapes, is called a pack if their point sets do not overlap. The subject of consideration here are only spheres of the same size. The name pack comes from the fact that such an arrangement defines exactly a certain area, the convex envelope of this pack. It is the smallest convex set that contains all spheres.

Pack forms

Balls can be arranged in different ways. A distinction is made between three basic types of packaging: sausage, pizza and cluster packs.

• 

  Sausage pack

• 

  Pizza pack

• 

  Cluster pack

Sausage pack

If the centers of the balls lie on a straight line, as shown in the first figure, one speaks of a sausage-shaped pack or sausage pack , since the casing here has the shape of a sausage. A rough example of this are commercial packs of tennis balls in a tube box. In fact, the two ends of the packaging should be rounded, which is usually not the case in reality.

Pizza pack

If the centers of the balls lie on one plane, one speaks of a pizza-shaped pack or pizza pack . Approximate examples of such packs in the real world can be found in chocolates or the ball pack in triangles, which are used to build billiard balls. This applies to packings in Euclidean spaces with three dimensions.

Cluster pack

If the center points lie anywhere in the room, one speaks of a cluster-shaped packing , cluster packing or simply of a cluster . Examples in the real world can be found with fruit, which is arranged in a box with rows and layers offset from one another.

Connections

According to this definition, a sausage pack is always a pizza pack and a pizza pack is always a cluster pack. In the general case of dimensions, one speaks of sausage in the case of a one-dimensional arrangement, of clusters in the case of a d-dimensional arrangement and of pizza for the dimensions in between. ${\displaystyle d}$

One or two balls always form a sausage pack. With three balls you can also create a pizza pack that is not a sausage pack. For four or more balls, there is also a cluster-shaped package that is not a pizza package.

Optimal packing

The size of the empty space between the balls varies depending on the shape of the pack. This is expressed in the packing density , the ratio of the volume of the spheres to the volume in the shell. The higher the packing density, the lower both the empty space of a pack and the volume in the casing (with the same number and thus constant total volume of the balls to be packed).

For economic reasons, a packing with the greatest possible packing density is now sought. It is immediately evident that a maximum packing density has the property that its objects lie close to one another, that is, they must touch one another on their surfaces. This can be expressed more precisely if one forms a graph for an arrangement that assigns a node to each object and then connects two nodes by an edge when they touch on their surfaces. The resulting graph must always be connected .

The sausage disaster

With three and four balls, the optimal pack is a sausage pack. It is assumed that this applies up to a number of and n = 57, 58, 63 and 64 balls. When , as Jörg Wills a cluster and Pier Mario Gandini 1992 showed tighter than a sausage package. What exactly this optimal cluster packing looks like is unknown. For example, it is not a tetrahedron arrangement as in the classical optimal packing of cannonballs, but probably an octahedron shape. ${\displaystyle n}$ ${\displaystyle 55}$ ${\displaystyle n=56,59,60,61,62{\text{ und }}n\geq 65}$ ${\displaystyle n=56}$

The sudden transition is jokingly referred to by mathematicians as the sausage disaster (Wills, 1985). The term catastrophe is based on the knowledge that the optimal arrangement changes suddenly from an ordered sausage pack to a relatively disordered cluster pack when changing from one number to the other , and this cannot be explained in a satisfactory manner. The transition in three dimensions is still relatively smooth; in dimensions, an abrupt transition from optimal sausage shape to cluster is assumed, at the latest, for balls. ${\displaystyle d=4}$ ${\displaystyle 375.370}$

For spherical packs in dimensions, either sausage or clusters are tightest packs, but never the pizza arrangement. This does not apply to the packing of other convex bodies. There is for every convex body for which the pizza is the closest packing ( Peter Gritzmann , Arhelger). ${\displaystyle d\leq 10}$ ${\displaystyle d\geq 3}$

Example of proof that a sausage pack is not optimal

The following shows that the sausage pack is not optimal for 455 balls, but that there is a special cluster pack that takes up less volume.

The volume of the convex shell of a sausage pack made of spheres with the radius can be calculated from elementary geometric bodies. The shell consists of a cylinder of height in the middle and a hemisphere with a radius at both ends . The volume of the convex envelope is therefore calculated using the following formula. ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle h=2r\cdot (n-1)}$ ${\displaystyle r}$ ${\displaystyle V_{W}}$

${\displaystyle {\begin{aligned}V_{W}&=V_{\text{Zylinder}}+2\cdot V_{\text{Halbkugel}}\\&=V_{\text{Zylinder}}+V_{\text{Kugel}}\\&=\pi hr^{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{aligned}}}$

Similarly, one can ask about the volume of the convex hull of a tetrahedron packing. In a tetrahedron packing, the spheres are piled up so that they take on the shape of a tetrahedron . A complete tetrahedron is of course only obtained for certain numbers of spheres. Be found along each edge of the tetrahedron balls, then the total number of stacked balls calculated by ${\displaystyle x}$ ${\displaystyle n}$

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

The incircular radius of a tetrahedron with edge length is ${\displaystyle r}$ ${\displaystyle a}$

${\displaystyle r={\frac {\sqrt {6}}{12}}\cdot a}$.

This can be to change ${\displaystyle a}$

${\displaystyle a=2{\sqrt {6}}\cdot r}$.

The volume of the tetrahedron is then given by the formula ${\displaystyle V_{T}}$

${\displaystyle V_{T}={\frac {\sqrt {2}}{12}}\cdot a^{3}={\sqrt {192}}\cdot r^{3}}$

given.

If you want to embed several spheres stacked to form a tetrahedron in a tetrahedron instead of a sphere, the edge length of the tetrahedron per layer is extended by twice the spherical radius, that is, an edge length of ${\displaystyle a}$ ${\displaystyle x}$

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

If you insert this into the volume formula for the tetrahedron, you get the estimate for the volume of the convex shell of the stacked spheres ${\displaystyle V}$

${\displaystyle V<{\frac {2\cdot \left(x-1+{\sqrt {6}}\right)^{3}\cdot {\sqrt {2}}\cdot r^{3}}{3}}}$.

If you now insert the formula for the number of spheres in layers into the formula for the volume of the casing of a sausage pack, you get the volume occupied by the sausage pack ${\displaystyle n}$ ${\displaystyle V_{\text{W}}}$

${\displaystyle V_{\text{W}}={\frac {x\cdot (x+1)\cdot (x+2)-2}{3}}\cdot \pi r^{3}}$,

which can now be compared with the estimate for the volume of the tetrahedron packing. For , i.e. balls, the prefactor for the estimation of the tetrahedral pack is less than 2845, while the prefactor for the volume of the sausage pack is greater than 2856. This proves that for 455 spheres the tetrahedron pack is denser than the sausage pack. ${\displaystyle x=13}$ ${\displaystyle n=455}$

With a little more effort, the exact formula can also be calculated instead of the estimate . All you have to do is subtract the excess volume at the corners and edges of the tetrahedron. This then allows the proof that the sausage pack is not the optimal pack even for smaller and therefore smaller associated numbers of balls. ${\displaystyle V}$ ${\displaystyle x}$ ${\displaystyle n}$

Sausage presumption

The name sausage comes from the mathematician László Fejes Tóth , who established the sausage presumption in 1975 . The optimal arrangement of spheres can be investigated in any dimension . Spheres, convex hulls and volumes can be formulated in any Euclidean space with more than one dimension. The generalized term of the sphere then denotes a -dimensional body in which all edge points are equidistant from its center, the respective number of spatial dimensions denoting. Fejes Tóth's sausage conjecture says that from a dimension of, the arrangement of balls along a straight line is always the best. Accordingly, the sausage disaster would no longer occur in a room with more than dimensions. Whether this is actually true is still unproven. The best result for this comes from Ulrich Betke and Martin Henk . In 1998 they proved that the sausage presumption actually applies from a dimension of . From the -dimensional space onwards, the sausage is always the closest arrangement and the sausage catastrophe does not occur. According to JM Wills, the optimal arrangement in two-dimensional space is always a cluster. ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle 5}$ ${\displaystyle 4}$ ${\displaystyle 42}$ ${\displaystyle 42}$

Interestingly, in three dimensions, the optimal pack always seems to be either a sausage or a cluster, but never a pizza. This fact also seems to hold in higher dimensions. It is assumed that an optimal arrangement always has "extreme" dimensions. Either the centers of the spheres lie on a line (one-dimensional) or they are generally arranged in a -dimensional cluster. ${\displaystyle n}$

Parametric density and methods used

It can be proven that the sausage pack for 56 balls is not optimal, and a better pack can also be specified. However, it is not known what the optimal pack looks like, even if there are assumptions about it. However, it is difficult to show that no better packing exists as this is an argument about all possible packing. The difficulties lie in the fact that there is no “simple” formula for the volume of a cluster. The optimality (or also non-optimality) is shown by suitable estimates of the volume. The methods for this come from convex geometry . Keywords for this are the Brunn-Minkowski inequality , mixed Minkowski volume and Steiner's formula . A decisive step towards a unified theory that includes both finite and infinite (lattice and non-lattice packing) was the introduction of a parametric density by Jörg Wills in 1992 (the parameter takes into account the influence of the edge of the packing).

The previously used notion of density went over the volume of the convex hull of the spheres (or convex bodies) : ${\displaystyle K}$

${\displaystyle \delta (K,C_{n})={\frac {nV(K)}{V(C_{n}+K)}}}$

with the convex hull of the centers of gravity of the spheres (spheres are considered here, but other convex bodies can also be considered). If there is a linear arrangement (sausage), the convex shell is a line that connects the centers of gravity. The plus sign in the formula is to be understood as a vector or Minkowski sum , so that the volume is the convex hull of the spheres. ${\displaystyle C_{n}}$ ${\displaystyle n}$ ${\displaystyle c_{i}}$ ${\displaystyle K_{i}}$ ${\displaystyle K}$ ${\displaystyle V(C_{n}+K)}$

This definition works in two dimensions, in which a unified theory of finite and infinite packing of spheres was created by Laszlo Fejes-Toth, Claude Rogers and others. In three dimensions one can give a simple argument (Wills) why a unified theory is not possible. The densest arrangement of circles, vividly like coins, is often the sausage there, which corresponds to the money rolls of the banks. Their density is (finite arrangement). Space-filling (infinite arrangement) is a hexagonal arrangement with a density of about . A way out offers a modified definition of density according to Wills with a positive parameter : ${\displaystyle \delta =1}$ ${\displaystyle 0{,}9}$ ${\displaystyle \rho }$

${\displaystyle \delta (K,C_{n})={\frac {nV(K)}{V(C_{n}+\rho K)}}}$

The parameter can be used to incorporate the influence of the edge (the convex hull is clearly given a certain thickness). The methods used then come from the theory of mixed volumes and the geometry of numbers by Hermann Minkowski . ${\displaystyle \rho }$

For each dimension there are parameter values and , so that for the sausage is the densest arrangement (for all numbers ) and for and for sufficiently large clusters are the densest arrangement. The parameter values and are each dimension-specific. The transition from the sausage to the cluster arrangement takes place in two dimensions (sausage disaster). ${\displaystyle d\geq 2}$ ${\displaystyle \rho _{s}(d)}$ ${\displaystyle \rho _{c}(d)}$ ${\displaystyle \rho \leq \rho _{s}(d)}$ ${\displaystyle n}$ ${\displaystyle \rho \geq \rho _{c}(d)}$ ${\displaystyle n}$ ${\displaystyle \rho _{s}(d)}$ ${\displaystyle \rho _{c}(d)}$ ${\displaystyle \rho _{c}(2)=\rho _{s}(2)={\frac {\sqrt {3}}{2}}}$

The inequality applies:

${\displaystyle {\frac {V(B^{d})}{2V(B^{d-1})}}{\rho _{c}(d)}^{1-d}\leq \delta (B^{d})\leq {\frac {V(B^{d})}{2V(B^{d-1})}}{\rho _{s}(d)}^{1-d}}$

with the volume of the unit ball in dimensions . For is and it is believed that this is true for all dimensions . The value of then follows from the determination of . ${\displaystyle B^{d}}$ ${\displaystyle d}$ ${\displaystyle V(B^{d})}$ ${\displaystyle d=2}$ ${\displaystyle \rho _{s}(d)=\rho _{c}(d)}$ ${\displaystyle d}$ ${\displaystyle \delta (B^{d})}$ ${\displaystyle \rho _{c}(d)}$

If one considers the closest lattice packing (lattice L) of spheres , then the normalized polytope in the limit only depends on and the lattice L and corresponds to the Wulff construction of crystals. ${\displaystyle C_{n,\rho }+\rho B^{d}}$ ${\displaystyle \rho \geq \rho _{c}(d)}$ ${\displaystyle {\frac {1}{n^{d}}}C_{n,\rho }}$ ${\displaystyle n\to \infty }$ ${\displaystyle \rho }$

Finite circular packs in containers

Various such problems, e.g. B. of circular packings on spherical surfaces or in squares were processed. Symmetry-free closest packings of congruent circles in squares could only be found with computer help. The work of a team led by Ronald Peikert at the ETH Zurich was fundamental for the proof of optimality . ${\displaystyle n}$ ${\displaystyle n>10}$

In this case there is only one closest packing in the unit square apart from congruence; this is symmetry-free and was found by K. Schlüter-Schmidtke in 1976 without the help of a computer. ${\displaystyle n=10}$

literature

• Max Leppmeier: Sphere packings and sausage disasters or on the theory of finite and infinite packings. In: A. Beutelspacher u. a. (Ed.), "Overview Mathematics 1996/1997", Braunschweig / Wiesbaden 1997, ISBN 3528068922
• Max Leppmeier: Ball packings from Kepler to this day. Vieweg, Braunschweig / Wiesbaden 1997, ISBN 3528067926
• Karoly Börözcky: Finite Packing and Covering , Cambridge University Press 2004
• L. Fejes Tóth Regular Figures Publishing House of the Hungarian Academy of Sciences Budapest 1965

Individual evidence

1. ↑ ^{a b c} J. M. Wills: Spheres and Sausages, Crystals and Catastrophes and a Joint Packing Theory . In: The Mathematical Intelligencer . tape 20 , no. 1 , March 1998, ISSN  0343-6993 , p. 16-21 , doi : 10.1007 / bf03024394 .
2. ↑ Wills, Math. Intelligencer, Volume 20, 1998, Issue 1, p. 18
3. ↑ Leppmeier, Kugelpackungen von Kepler bis today, Vieweg 1997, p. 121
4. ^ Pier Mario Gandini, Jörg Michael Wills: On finite sphere packings. In: Math. Pannonica 3, No. 1, 1992, pp. 19-20
5. ↑ Max Leppmeier: Ball packings from Kepler until today. Vieweg, Braunschweig / Wiesbaden 1997, p. 121
6. ^ Wills, Gritzmann, Finite packing and covering, in Gruber, Wills, Handbook of convex geometry, Part B, North Holland 1993, p. 871
7. ↑ Wills, Math. Intelligencer, Volume 20, 1998, Issue 1, p. 18
8. ↑ Wills, Math. Intelligencer, 1998, p. 19
9. ↑ László Fejes Tóth : Research Problem 13. In: Period. Math. Hungar. Vol. 6, 1975, pp. 197-199
10. ↑ Ulrich Betke, Martin Henk: Finite Packings of Spheres. In: Discr. Comput. Geom Vol. 19, 1998, pp. 197-227
11. ^ JM Wills, "Finite Sphere Packings and Sphere Coverings". Proceedings of the Geometry Conference in Cagliari, May 1992 ( on-line PDF )
12. ^ Wills, Kugelpackungen - Old and New, DMV Mitteilungen 4/95, p. 21
13. ↑ See Leppmeier, Kugelpackungen von Kepler bis heute, pp. 145ff
14. ↑ Representation in this section according to Wills, Kugelpackungen- Altes und Neues, Mitt.DMV 1995, No. 4
15. ↑ Peikert, Ronald. "Closest packs of equal circles in a square .." Elements of Mathematics 49.1 (1994): 16-26.

This article was added to the list of articles worth reading on June 15, 2005 in this version .