Die mathematische Theorie der endlichen Kugelpackungen beschäftigt sich mit der Frage, wie eine endliche Anzahl gleich großer Kugeln möglichst platzsparend verpackt werden kann. Endliche Kugelpackungen sind erst in den letzten Jahrzehnten mathematisch genauer untersucht worden. László Fejes Tóth hat dazu wichtige Grundsteine gelegt.

Eine weitaus längere Tradition hat dagegen das Problem der dichtesten Packung für unendliche Kugelpackungen. Die berühmteste Vermutung hierzu ist die Keplersche Vermutung. Atome in Kristallstrukturen können vereinfacht als Kugelpackungen betrachtet werden und aufgrund ihrer hohen Anzahl kann man sie als gute Annäherung an unendliche Kugelpackungen auffassen.

Bei den Problemen unterscheidet man Packungen in einen vorgegebenen konvexen Körper (Container, Bin-Packung, siehe auch Behälterproblem) und freie Packungen. Hier wird im Folgenden (bis auf den letzten Abschnitt) überwiegend das Problem freier endlicher Packungen behandelt.

Packung und konvexe Hülle

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 gleich große Kugeln. Der Name Packung rührt nun daher, dass durch eine solche Anordnung exakt ein bestimmtes Gebiet, die konvexe Hülle dieser Packung, festgelegt ist. Sie ist die kleinste konvexe Menge, die alle Kugeln enthält.

Packungsformen

Kugeln kann man auf verschiedene Weise anordnen. Man unterscheidet dabei zwischen drei grundlegenden Packungsformen: der Wurst-, Pizza- und Clusterpackung.

• Wurstpackung
• Pizzapackung
• Clusterpackung

Optimale Packung

Abhängig von der Packungsform ist der Leerraum zwischen den Kugeln unterschiedlich groß. Dies kommt in der Packungsdichte zum Ausdruck, dem Verhältnis des Volumens der Kugeln zum Volumen in der Hülle. Je höher die Packungsdichte, desto geringer ist sowohl der Leerraum einer Packung, als auch das Volumen in der Hülle (bei gleichbleibender Anzahl und damit gleichbleibendem Gesamtvolumen der zu verpackenden Kugeln).

Aus ökonomischen Gründen ist nun eine Packung mit größtmöglicher Packungsdichte gesucht. Es ist unmittelbar einsichtig, dass eine maximale Packungsdichte die Eigenschaft besitzt, dass ihre Objekte dicht aneinander liegen, das heißt, sie müssen einander 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.

Die Wurstkatastrophe

Bei drei und vier Kugeln ist die optimale Packung eine Wurstpackung. Man vermutet, dass dies bis zu einer Anzahl ${\displaystyle n}$ von ${\displaystyle 55}$ sowie ${\displaystyle n=57,58,63{\text{ und }}64}$ Kugeln gilt. Bei ${\displaystyle n=56,59,60,61,62{\text{ und }}n\geq 65}$ ist, wie Jörg Wills und Pier Mario Gandini 1992 zeigten, ein Cluster dichter als eine Wurstpackung. Wie diese optimale Clusterpackung genau aussieht, ist unbekannt. Zum Beispiel ist sie für ${\displaystyle n=56}$ keine Tetraederanordnung wie bei der klassischen optimalen Packung von Kanonenkugeln, sondern wahrscheinlich von Oktaeder-Form.

Der plötzliche Übergang wird von Mathematikern scherzhaft als Wurstkatastrophe bezeichnet (Wills, 1985). Die Bezeichnung Katastrophe beruht auf der Erkenntnis, dass sich die optimale Anordnung beim Übergang von einer zur anderen Anzahl schlagartig von einer geordneten Wurstpackung in eine relativ ungeordnete Clusterpackung ändert und umgekehrt, ohne dass sich dies in befriedigender Weise erklären lässt. Dabei ist der Übergang in drei Dimensionen noch relativ gleitend, in ${\displaystyle d=4}$ Dimensionen wird ein sprunghafter Übergang von optimaler Wurstform zu Cluster spätestens bei ${\displaystyle 375.370}$ Kugeln vermutet.

Für Kugelpackungen in ${\displaystyle d\leq 10}$ Dimensionen sind entweder Wurst oder Cluster dichteste Packungen, aber niemals die Pizza-Anordnung. Das gilt nicht für die Packung anderer konvexer Körper. Es gibt für jedes ${\displaystyle d\geq 3}$ konvexe Körper, für die die Pizza die dichteste Packung ist (Peter Gritzmann, Arhelger).

Parametrische Dichte und verwendete Methoden

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 Konvexgeometrie. Stichworte dazu sind Brunn-Minkowski-Ungleichung, gemischtes Minkowski-Volumen und Formel von Steiner. Ein entscheidender Schritt zu einer vereinheitlichten Theorie, die sowohl endliche als auch unendliche (Gitter- und Nicht-Gitterpackungen) umfasst, war die Einführung einer parametrischen Dichte durch Jörg Wills 1992 (der Parameter berücksichtigt den Einfluss des Randes der Packung).

Der zuvor benutzte Dichtebegriff ging über das Volumen der konvexen Hülle der Kugeln (oder konvexen Körper) ${\displaystyle K}$:

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

mit ${\displaystyle C_{n}}$ der konvexen Hülle der ${\displaystyle n}$ Schwerpunkte ${\displaystyle c_{i}}$ der Kugeln ${\displaystyle K_{i}}$ (hier werden Kugeln betrachtet, man kann aber auch andere konvexe Körper ${\displaystyle K}$ betrachten). Liegt eine lineare Anordnung (Wurst) vor, ist die konvexe Hülle eine Strecke, die die Schwerpunkte verbindet. Das Pluszeichen in der Formel ist als Vektor- oder Minkowski-Summe aufzufassen, so dass ${\displaystyle V(C_{n}+K)}$ das Volumen der konvexen Hülle der Kugeln ist.

Diese Definition funktioniert in zwei Dimensionen, in der damit durch Laszlo Fejes-Toth, Claude Rogers und andere eine vereinheitlichte Theorie endlicher und unendlicher Kugelpackungen geschaffen wurde. In drei Dimensionen kann man ein einfaches Argument angeben (Wills), warum eine einheitliche Theorie nicht möglich ist. Die dichteste Anordnung von Kreisen, anschaulich etwa Geldmünzen, ist dort vielfach die Wurst. Deren Dichte ist ${\displaystyle \delta =1}$ (Endliche Anordnung). Raumfüllend (unendliche Anordnung) ist aber eine hexagonale Anordnung mit einer Dichte von etwa ${\displaystyle 0{,}9}$. Einen Ausweg bietet eine modifizierte Definition der Dichte nach Wills mit einem positiven Parameter ${\displaystyle \rho }$:

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

Mit dem Parameter ${\displaystyle \rho }$ kann man den Einfluss des Randes einfließen lassen (anschaulich erhält so die konvexe Hülle eine bestimmte Dicke). Die angewandten Methoden stammen dann aus der Theorie gemischter Volumina und der Geometrie der Zahlen von Hermann Minkowski.

Für jede Dimension ${\displaystyle d\geq 2}$ gibt es Parameterwerte ${\displaystyle \rho _{s}(d)}$ und ${\displaystyle \rho _{c}(d)}$, so dass für ${\displaystyle \rho \leq \rho _{s}(d)}$ die Wurst die dichteste Anordnung ist (für alle Anzahlen ${\displaystyle n}$) und für ${\displaystyle \rho \geq \rho _{c}(d)}$ und für hinreichend große ${\displaystyle n}$ Cluster die dichteste Anordnung sind. Die Parameterwerte ${\displaystyle \rho _{s}(d)}$ und ${\displaystyle \rho _{c}(d)}$ sind jeweils dimensionsspezifisch. In zwei Dimensionen ist ${\displaystyle \rho _{c}(2)=\rho _{s}(2)={\frac {\sqrt {3}}{2}}}$ und dort findet der Übergang von der Wurst zur Cluster-Anordnung statt (Wurstkatastrophe).

Es gilt die Ungleichung:

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

mit dem Volumen des Einheitsballs ${\displaystyle B^{d}}$ in ${\displaystyle d}$ Dimensionen ${\displaystyle V(B^{d})}$. Für ${\displaystyle d=2}$ ist ${\displaystyle \rho _{s}(d)=\rho _{c}(d)}$ und es wird vermutet, dass das für alle Dimensionen ${\displaystyle d}$ gilt. Aus der Bestimmung von ${\displaystyle \delta (B^{d})}$ folgt dann der Wert von ${\displaystyle \rho _{c}(d)}$.

Betrachtet man eine dichteste Gitterpackung (Gitter L) von Kugeln ${\displaystyle C_{n,\rho }+\rho B^{d}}$, so ist für ${\displaystyle \rho \geq \rho _{c}(d)}$ so hängt das normierte Polytop ${\displaystyle {\frac {1}{n^{d}}}C_{n,\rho }}$ im Grenzfall ${\displaystyle n\to \infty }$ nur von ${\displaystyle \rho }$ und dem Gitter L ab und entspricht der Wulff-Konstruktion von Kristallen.

Endliche Kreispackungen in Containern

Verschiedene solcher Problemstellungen, z. B. von Kreispackungen auf Kugeloberflächen oder in Quadraten, wurden bearbeitet. Symmetriefreie dichteste Packungen von ${\displaystyle n}$ kongruenten Kreisen in Quadraten konnten für ${\displaystyle n>10}$ nur mit Computerhilfe gefunden werden. Grundlegend für die Optimalitätsbeweise war die Arbeit eines Teams um Ronald Peikert an der ETH Zürich.

Für den Fall ${\displaystyle n=10}$ gibt es im Einheitsquadrat bis auf Kongruenz nur eine dichteste Packung; diese ist symmetriefrei und wurde von K. Schlüter-Schmidtke 1976 ohne Computerhilfe gefunden.

Literatur

• 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. Vieweg, Braunschweig/Wiesbaden 1997, ISBN 3528067926
• Karoly Börözcky: Finite Packing and Covering, Cambridge University Press 2004
• L. Fejes Tóth Reguläre Figuren Verlag der ungarischen Akademie der Wissenschaften Budapest 1965

Einzelnachweise

1. 1 2 3 J. M. Wills: Spheres and Sausages, crystals and catastrophes- and a joint packing theory. In: The Mathematical Intelligencer. Band 20, Nr. 1, März 1998, ISSN 0343-6993, S. 16–21, doi:10.1007/bf03024394. 
2. ↑ Wills, Math. Intelligencer, Band 20, 1998, Heft 1, S. 18
3. ↑ Leppmeier, Kugelpackungen von Kepler bis heute, Vieweg 1997, S. 121
4. ↑ Pier Mario Gandini, Jörg Michael Wills: On finite sphere-packings. In: Math. Pannonica 3, Nr. 1, 1992, S. 19–20
5. ↑ Max Leppmeier: Kugelpackungen von Kepler bis heute. Vieweg, Braunschweig/Wiesbaden 1997, S. 121
6. ↑ Wills, Gritzmann, Finite packing and covering, in Gruber, Wills, Handbook of convex geometry, Teil B, North Holland 1993, S. 871
7. ↑ Wills, Math. Intelligencer, Band 20, 1998, Heft 1, S. 18
8. ↑ Wills, Math. Intelligencer, 1998, S. 19
9. ↑ László Fejes Tóth: Research Problem 13. In: Period. Math. Hungar. Bd. 6, 1975, S. 197–199
10. ↑ Ulrich Betke, Martin Henk: Finite Packings of spheres. In: Discr. Comput. Geom Bd. 19, 1998, S. 197–227
11. ↑ J. M. Wills, "Finite Sphere Packings and Sphere Coverings". Proceedings of the Geometry Conference in Cagliari, May 1992 (on-line PDF)
12. ↑ Wills, Kugelpackungen – Altes und Neues, DMV Mitteilungen 4/95, S. 21
13. ↑ Siehe Leppmeier, Kugelpackungen von Kepler bis heute, S. 145ff
14. ↑ Darstellung in diesem Abschnitt nach Wills, Kugelpackungen – Altes und Neues, Mitt. DMV 1995, Nr. 4
15. ↑ Peikert, Ronald. "Dichteste Packungen von gleichen Kreisen in einem Quadrat." Elemente der Mathematik 49.1 (1994): 16-26.