Theorie der endlichen Kugelpackungen

Die Theorie der endlichen Kugelpackungen ist ein Gebiet der Mathematik, welches sich mit der Frage beschäftigt, wie eine endliche Menge von Kugeln optimal, also möglichst platzsparend, verpackt werden kann. Endliche Kugelpackungen sind erst in den letzten Jahrzehnten mathematisch genauer untersucht worden. Fejes Toth hat dazu wichtige Grundsteine gelegt.

Eine weitaus längere Tradition haben dagegen unendliche Kugelpackungen. Das Problem der dichtesten Anordnung kann man auch für eine unendliche Anzahl von Kugeln betrachten. Hier geht es darum, diejenige Anordnung von Kugeln zu finden, bei der am wenigsten Zwischenraum bleibt. Die berühmteste Vermutung hierzu ist die Keplersche Vermutung. Kugelpackungen haben ihre Anwendung in der Kristallographie.

Wurst- packung

Allgemein und anschaulich bezeichnet man eine beliebige Anordnung einer Menge von räumlich zusammenhängenden, möglicherweise verschiedengroßen und verschiedenförmigen Objekten im Raum als Packung, wenn sich ihre Punktmengen nicht überschneiden. Gegenstand der Betrachtung hier sind aber lediglich gleichgroße Kugeln. Der Name Packung rührt nun daher, dass durch eine solche Anordnung exakt ein bestimmtes Gebiet, die sogenannte Hülle dieser Packung, festgelegt ist. Sie besteht aus allen Punkten, die auf einer Gerade zwischen je zwei beliebigen Punkten der Objektmenge liegen. Da dieses Gebiet immer konvex (also nach außen, nie nach innen gewölbt ist) nennt man dieses Gebiet auch exakter konvexe Hülle. Im Bild entspricht das der Menge, die durch die blaue Linie begrenzt wird.

Aus ökonomischen Gründen ist nun eine Packung, also eine entsprechende Anordnung gesucht, die das Volumen der zugehörigen Hülle minimiert. Damit ist auch gleichzeitig immer der Leerraum, also das Volumen des nicht von den Objekten genutzten Platzes, minimal und die Packungsdichte, also das Verhältnis aus dem immer gleichen Volumen der Objekte zur variablen Größe der Hülle, maximal.

Es ist unmittelbar einsichtig, dass eine minimale Packungsdichte die Eigenschaft besitzt, dass ihre Objekte dicht aneinander liegen, das heißt, sie müssen sich an ihren Oberflächen berühren. Exakter lässt sich dies ausdrücken, wenn man zu einer Anordnung einen Graphen bildet, der jedem Objekt einen Knoten zuordnet und zwei Knoten dann durch eine Kante verbindet, wenn sie sich an ihren Oberflächen berühren. Der so entstehende Graph muss immer zusammenhängend sein.

Der Leerraum bzw. die Packungsdichte hängt von der Anordnung der Objekte ab. Für Kugeln kann nun in drei prinzipielle Packungsformen unterschieden werden:

• Liegen die Mittelpunkte der Kugeln auf einer geraden Linie wie in der ersten Abbildung dargestellt, so spricht man von einer wurstförmigen Packung oder Wurstpackung, da die Hülle hier die Form einer Wurst besitzt. Ein ungefähres Beispiel hierfür sind handelsübliche Packungen von Tennisbällen in einem Röhren-Karton. Tatsächlich müssten die beiden Enden der Verpackung abgerundet sein, was in der Realität aber meist nicht der Fall ist.
• Liegen die Mittelpunkte der Kugeln auf einer Ebene, so spricht man von einer pizzaförmigen Packung oder Pizzapackung. Ungefähre Beispiele für derartige Packungen in der realen Welt findet man bei Pralinen.
• Liegen die Mittelpunkte beliebig im Raum, so spricht man von einer clusterförmigen Packung, Clusterpackung oder schlicht von einem Cluster. Beispiele in der realen Welt findet man bei Obst, welches in einer Kiste mit gegeneinander versetzten Reihen angeordnet wird.

Clusterpackung

Zu beachten ist, dass nach dieser Definition eine Wurstpackung auch immer eine Pizzapackung darstellt und eine Pizzapackung auch immer eine Clusterpackung ist.

Man sieht leicht, dass eine oder zwei Kugeln immer eine Wurstpackung bilden. Mit drei Kugeln lässt sich auch eine Pizzapackung realisieren, die keine Wurstpackung darstellt. Ab vier Kugeln existiert auch eine clusterförmige Packung, die keine Pizzapackung darstellt.

Werden drei Kugeln aneinander gereiht und mit einer elastischen Wurstpelle – wie in der ersten Abbildung für sechs Kugeln gezeigt – verpackt, hat der Leerraum ein optimales Volumen, das heißt jede andere clusterförmigen Packung besitzt mehr Leerraum, auch wenn die zweidimensionalen Darstellungen das Gegenteil zu zeigen scheinen.

Bei drei Kugeln ist die beste Anordnung eine Wurstpackung. Diese Regel behält ihre Gültigkeit zunächst auch bei einer ansteigenden Kugelzahl. Mit 56 Kugeln existiert jedoch eine Kugelzahl, für die bekannt ist, dass die ökonomischste Packung keine Wurstpackung mehr ist. Tatsächlich gilt dies sogar für alle Zahlen, die größer als 56 sind.

Dieser Übergang wird von Mathematikern scherzhaft als Wurstkatastrophe bezeichnet. Die Bezeichnung Katastrophe beruht auf der Erkenntnis, dass sich die optimale Anordnung von einer zur anderen Packungsform schlagartig von einer geordneten Wurstpackung in eine relativ ungeordnete Clusterpackung ändert.

Eine optimale Anordnung für Kugeln zu finden ist ein mathematisch herausforderndes Problem. Jörg Wills hat 1985 die Vermutung aufgestellt, dass bis zu einer gewissen Anzahl von Kugeln die Anordnung als Wurst optimal ist, während ab einer (möglicherweise größeren) Zahl eine Clusterpackung die beste ist, die weder Wurst- noch Pizzapackung darstellt. Die kleinste Zahl, ab der die Wurstpackung nicht mehr optimal ist, entspricht der Kugelzahl, ab der die Wurstkatastrophe eintritt. Diese Vermutung ist teilweise bewiesen worden: 1992 konnten Pier Mario Gandini und Jörg Michael Wills zeigen ([2]), dass ab 56 Kugeln mit den Ausnahmen 57, 58, 63, 64 die lineare Anordnung als Wurst nicht die beste ist, sondern in diesem Fall eine Clusterpackung besser ist, die keine Wurstpackung darstellt. Mittlerweile konnte auch für diese vier Ausnahmen gezeigt werden, dass die Wurstverpackung nicht optimal ist. Damit tritt die Wurstkatastrophe auf jeden Fall bei höchstens 56 Kugeln ein.

Es wird zwar allgemein angenommen, dass bei weniger als 56 Kugeln die Wurst optimal ist, aber ein Beweis dafür steht noch aus (Quelle: [3]).

Im folgenden wird gezeigt, dass die optimale Wurstpackung für 455 Kugeln nicht optimal ist, sondern eine spezielle Clusterpackung existiert, die weniger Volumen einnimmt.

Das Volumen ${\displaystyle V_{W}}$ der konvexen Hülle einer optimalen Wurstpackung von n Kugeln lässt sich relativ leicht berechnen. Ist r der Kugelradius, so besteht die Hülle aus einem Zylinder der Höhe ${\displaystyle h=2r\cdot (n-1)}$ und Radius r sowie zwei Halkugeln mit Radius r an dessen Enden. ${\displaystyle V_{W}}$ ergibt sich somit aus der Summe der Volumina des Zylinders und einer Kugel vom Radius r. Das Volumen ${\displaystyle V_{Z}}$ des Zylinders mit der Höhe h und dem Radius r ist daher

${\displaystyle V_{Z}=\pi hr^{2}=2\pi \cdot (n-1)\cdot r^{3}.}$

Das Volumen ${\displaystyle V_{K}}$ einer Kugel mit Radius r ist gegeben durch

${\displaystyle V_{K}={\frac {4}{3}}\pi r^{3}.}$

Daraus folgt dann für das Volumen der konvexen Hülle einer optimalen Wurstpackung

${\displaystyle V_{W}=V_{Z}+V_{K}=2\cdot \left(n-{\frac {1}{3}}\right)\pi r^{3}.}$

Ähnlich kann man nach dem Volumen der konvexen Hülle einer Tetraederpackung fragen. Bei einer Tetraederpackung werden die Kugeln so aufgeschichtet, dass sie die Form eines Tetraeders annehmen. Ein vollständiger Tetraeder ergibt sich dabei natürlich nur für bestimmte Kugelzahlen. Findet man entlang jeder Kante des Tetraeders x Kugeln, so berechnet sich die Gesamtzahl der aufgeschichteten Kugeln n durch

${\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}}.}$

Der Inkugelradius r eines Tetraeders mit Kantenlänge a ist

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

Dies lässt sich nach a umstellen

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

Das Volumen ${\displaystyle V_{T}}$ des Tetraeders ist dann durch die Formel

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

gegeben.

Will man statt einer Kugel mehrere zu einem Tetraeder aufgeschichtete Kugeln in einen Tetraeder einbetten, so verlängert sich die Kantenlänge a des Tetraeders pro Schicht um das doppelte des Kugelradius, dass heißt bei x Schichten ergibt sich eine Kantenlänge von

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

Setzt man dies wieder in die Volumenformel für das Tetraeder ein, so erhält man für das Volumen V der konvexen Hülle der aufgeschichteten Kugeln die Abschätzung:

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

Setzt man nun die Formel für die Anzahl der Kugeln bei n Schichten in die Formel für das Volumen ${\displaystyle V_{W}}$ der Hülle einer optimalen Wurstpackung ein, erhält man das von der Wurstpackung eingenommene Volumen

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

das sich nun mit der Abschätzung für das Volumen der Tetraederpackung vergleichen lässt. Für x=13, also n=455 Kugeln ist der Vorfaktor für die Abschätzung der Tetraederpackung kleiner als 2845, während der Vorfaktor für das Volumen der optimalen Wurstpackung größer als 2856 ist. Dies beweist, das für 455 Kugeln die Tetraederpackung dichter als die Wurstpackung ist.

Mit etwas mehr Aufwand lässt sich statt der Abschätzung für V auch die exakte Formel berechnen. Dazu muss nur das überschüssige Volumen an den Ecken und Kanten des Tetraeders abgezogen werden. Dies lässt dann auch für kleinere x und damit kleinere zugehörige Kugelzahlen n den Nachweis zu, dass die optimale Wurstpackung nicht die optimale Packung darstellt.

Die Bezeichnung Wurst stammt vom Mathematiker Laszlo Fejes Toth; er stellte 1975 die Wurstvermutung auf ([1]). Die optimale Anordnung von Kugeln kann man auch in höheren Dimensionen untersuchen. Die Definition von Kugeln, konvexer Hülle sowie Volumen kann völlig analog auch in einem euklidischen Raum mit mehr als drei Dimensionen formuliert werden. Die Wurstvermutung von Toth besagt, dass ab einer Dimension von 5 die Anordnung von Kugeln entlang einer Geraden immer die Beste ist. Demnach würde die Wurstkatastrophe in einem Raum mit mehr als 4 Dimensionen nicht mehr auftreten. Ob dies tatsächlich stimmt ist noch unbewiesen. Das beste Resultat hierzu stammt von Ulrich Betke und Martin Henk ([4]). Sie bewiesen 1998, dass ab einer Dimension von 42 die Wurstvermutung tatsächlich gilt. Ab dem 42-dimensionalen Raum ist die Wurst also immer die dichteste Anordnung und die Wurstkatastrophe tritt nicht ein.

Interessanterweise scheint in drei Dimensionen die optimale Packung immer entweder eine Wurst oder ein Cluster, aber niemals eine Pizza zu sein. Auch diese Tatsache scheint in höheren Dimensionen zu gelten. Es wird vermutet, dass eine optimale Anordnung immer „extreme“ Dimensionen aufweist. Entweder liegen die Kugelmittelpunkte auf einer Linie (eindimensional) oder sie sind allgemein in einem n-dimensionalen Cluster angeordnet.

Es lässt sich zwar beweisen, dass die Wurstpackung für 56 Kugeln nicht optimal ist und es lässt sich auch eine bessere Packung angeben. Wie die optimale Packung aussieht, ist aber nicht bekannt, auch wenn Vermutungen darüber existieren. Es ist aber schwierig zu zeigen, dass keine bessere Packung existiert, da dies ein Argument über alle möglichen Packungen darstellt. Die Schwierigkeiten liegen schon darin begründet, dass es keine „einfache“ Formel für das Volumen eines Clusters gibt. Die Optimalität (oder auch Nichtoptimalität) wird durch geeignete Abschätzungen des Volumens gezeigt. Die Methoden dafür kommen aus der konvexen Geometrie. Stichworte dazu sind Brunn-Minkowski-Ungleichung, gemischtes Minkowski-Volumen und Formel von Steiner.

• Max Leppmeier, „Kugelpackungen und Wurstkatastrophen oder zur Theorie der finiten und infiniten Packungen“, in: A. Beutelspacher u.a. (Hrsg.), „Überblick Mathematik 1996/1997“, Braunschweig/Wiesbaden 1997, ISBN 3528068922
• Max Leppmeier, „Kugelpackungen von Kepler bis heute“, Braunschweig/Wiesbaden 1997, ISBN 3528067926

• [1] L. Fejer Toth, „Research Problem 13“, Period. Math. Hungar 6, 197-199 (1975)
• [2] P.M. Gandini, J.M. Wills, „On finite sphere-packings“ Math. Pannonica 3, Nr. 1, pp, 19-20, (1992)
• [3] J.M. Wills, „Spheres and sausages, crystal and catastrophes – and a joint packing theory“, Math. Intelligencer 20, No. 1, pp 16-21 (1998)
• [4] U. Betke, M. Henk, „Finite Packings of spheres“ Discr. Comput. Geom 19, pp 197-227 (1998)

• U. Betke, M. Henk, J. Wills „(In)Finite packings“, Verlag Vieweg. ISBN 3-528-06797-7