Theorie der endlichen Kugelpackungen

Gegenstand und Grundbegriffe

Die Theorie der endlichen Kugelpackungen untersucht, wie endlich viele gleich große Kugeln möglichst platzsparend angeordnet werden können. Entscheidend ist dabei die konvexe Hülle: die kleinste konvexe Menge, die alle Kugeln enthält. Eine Packung ist allgemein eine Anordnung räumlich zusammenhängender Objekte, deren Punktmengen sich nicht überschneiden; hier werden jedoch nur gleich große Kugeln betrachtet.

Gesucht ist meist eine freie Packung, also ohne vorgegebenen Behälter. Davon zu unterscheiden sind Packungen in einem konvexen Container, auch Bin-Packungen genannt. Im Unterschied zu endlichen Packungen hat die dichteste unendliche Kugelpackung eine längere Forschungstradition; die Keplersche Vermutung wurde 1998 von Thomas Hales bewiesen. Kristallstrukturen von Atomen lassen sich vereinfacht als nahezu unendliche Kugelpackungen auffassen.

Die Packungsdichte ist das Verhältnis aus dem Volumen aller Kugeln und dem Volumen ihrer konvexen Hülle. Bei gleicher Kugelzahl bedeutet eine höhere Dichte weniger Leerraum und eine kleinere Hülle. In einer maximal dichten Packung berühren sich die Kugeln so, dass der Berührungsgraph zusammenhängend ist: Jeder Kugel entspricht ein Knoten, und eine Kante verbindet zwei Knoten genau dann, wenn die Kugeln einander an der Oberfläche berühren.

Grundformen von Packungen

Es gibt drei grundlegende Formen, die durch die Lage der Kugelmittelpunkte bestimmt werden:

• Bei einer Wurstpackung liegen alle Mittelpunkte auf einer Geraden. Ihre Hülle ist wurstförmig; Tennisbälle in einem Röhrenkarton sind ein ungefähres Alltagsbeispiel.
• Bei einer Pizzapackung liegen die Mittelpunkte auf einer Ebene. Pralinenanordnungen oder dreieckige Billardkugel-Anordnungen sind ungefähre Beispiele im dreidimensionalen euklidischen Raum.
• Bei einer Clusterpackung sind die Mittelpunkte im dreidimensionalen Raum verteilt. Versetzt gestapeltes Obst in einer Kiste veranschaulicht diese Form.

Die Begriffe sind ineinander enthalten: Jede Wurstpackung ist auch eine Pizzapackung, und jede Pizzapackung ist auch ein Cluster. In d Dimensionen heißt eine eindimensionale Anordnung Wurst, eine d-dimensionale Anordnung Cluster; die zwischenliegenden Dimensionen werden Pizza genannt. Eine oder zwei Kugeln bilden stets eine Wurst. Bei drei Kugeln ist eine Pizza möglich, die keine Wurst ist; ab vier Kugeln gibt es einen Cluster, der keine Pizza ist.

Wurstkatastrophe und Wurstvermutung

Für drei und vier Kugeln ist die Wurstpackung optimal. Es wird vermutet, dass dies bis n = 55 sowie für n = 57, 58, 63 und 64 gilt. Für n = 56, 59, 60, 61, 62 und n ≥ 65 zeigten Jörg Wills und Pier Mario Gandini 1992, dass ein Cluster dichter als eine Wurstpackung ist. Die genaue optimale Clusterform ist dabei nicht bekannt. Für n = 56 ist sie beispielsweise keine Tetraederanordnung wie bei der klassischen Kanonenkugelpackung, sondern wahrscheinlich oktaederförmig.

Der abrupte Wechsel zwischen Wurst und Cluster heißt scherzhaft Wurstkatastrophe. Mit veränderter Kugelzahl kann die optimale Form plötzlich von einer geordneten linearen Anordnung zu einem Cluster wechseln oder umgekehrt. In drei Dimensionen ist dieser Übergang noch relativ gleitend. Für d = 4 wird spätestens bei 375 370 Kugeln ein sprunghafter Übergang von Wurst zu Cluster vermutet.

Für d ≤ 10 sind Wurst oder Cluster die dichtesten Kugelpackungen, niemals Pizza. Für andere konvexe Körper gilt dies nicht: Für jedes d ≥ 3 gibt es konvexe Körper, bei denen Pizza am dichtesten ist.

Die 1975 von László Fejes Tóth formulierte Wurstvermutung behauptet, dass ab Dimension 5 die lineare Wurstpackung immer optimal sei; die Wurstkatastrophe träte dann oberhalb von vier Dimensionen nicht auf. Dies ist unbewiesen. Ulrich Betke und Martin Henk bewiesen 1998 jedoch, dass die Vermutung ab Dimension 42 gilt. Im zweidimensionalen Raum ist nach J. M. Wills immer ein Cluster optimal. Allgemein wird vermutet, dass optimale Anordnungen nur extreme Dimensionen haben: entweder eine Gerade oder ein voller d-dimensionaler Cluster, nie eine Pizza.

Beweisidee mit 455 Kugeln

Für eine Wurst aus n Kugeln mit Radius r besteht die konvexe Hülle aus einem Zylinder der Höhe h = 2r · (n − 1) und zwei Halbkugeln. Ihr Volumen lautet

V_W = 2 · (n − 1/3)πr³.

Eine Tetraederpackung entsteht durch das Aufschichten von Kugeln in Tetraederform. Bei x Kugeln entlang jeder Kante beträgt die Kugelzahl

n = x(x + 1)(x + 2)/6.

Für einen Tetraeder mit Kantenlänge a gilt für seinen Inkugelradius r: r = (√6/12) · a, also a = 2√6 · r. Werden x Schichten von Kugeln eingebettet, ist die Kantenlänge a = 2 · (x − 1 + √6) · r. Daraus folgt für das Volumen V der konvexen Hülle die Abschätzung

V < 2(x − 1 + √6)³√2r³/3.

Setzt man die Kugelzahl der Tetraederpackung in die Wurstformel ein, erhält man

V_W = [x(x + 1)(x + 2) − 2]πr³/3.

Für x = 13 und damit n = 455 ist der Vorfaktor der Tetraeder-Abschätzung kleiner als 2845, derjenige der Wurst größer als 2856. Daher nimmt die Tetraederpackung weniger Volumen ein und ist dichter als die Wurstpackung. Eine exakte Volumenformel erhält man, wenn überschüssiges Volumen an Ecken und Kanten abgezogen wird; damit lässt sich die Nichtoptimalität der Wurst auch für kleinere Kugelzahlen zeigen.

Parametrische Dichte und Methoden

Eine bessere Packung anzugeben beweist noch nicht, wie die optimale Packung aussieht: Dafür müsste man alle möglichen Packungen ausschließen. Besonders schwierig ist, dass es keine einfache Formel für das Volumen eines Clusters gibt. Abschätzungen stammen aus der Konvexgeometrie, unter anderem aus der Brunn-Minkowski-Ungleichung, dem gemischten Minkowski-Volumen und der Formel von Steiner.

Der frühere Dichtebegriff lautet δ(K,C_n) = nV(K)/V(C_n + K). Dabei ist C_n die konvexe Hülle der n Kugelschwerpunkte c_i, K ein konvexer Körper und „+“ die Minkowski-Summe. Somit ist V(C_n + K) das Volumen der konvexen Hülle der Kugeln. In zwei Dimensionen führte dies zu einer einheitlichen Theorie endlicher und unendlicher Packungen. In drei Dimensionen ist das nicht unmittelbar möglich: Eine endliche Wurst aus Kreisen hat Dichte δ = 1, während die raumfüllende hexagonale Anordnung etwa die Dichte 0,9 besitzt.

Jörg Wills führte 1992 deshalb die parametrische Dichte δ(K,C_n) = nV(K)/V(C_n + ρK) mit ρ > 0 ein. Der Parameter ρ berücksichtigt den Randeinfluss, indem die konvexe Hülle anschaulich eine bestimmte Dicke erhält. Für jede Dimension d ≥ 2 gibt es dimensionsspezifische Werte ρ_s(d) und ρ_c(d): Für ρ ≤ ρ_s(d) ist die Wurst für alle n am dichtesten; für ρ ≥ ρ_c(d) sind bei hinreichend großem n Cluster am dichtesten. In zwei Dimensionen gilt ρ_c(2) = ρ_s(2) = √3/2; dort liegt der Übergang von Wurst zu Cluster.

Es gilt

[V(B^d)/(2V(B^(d−1)))]ρ_c(d)^(1−d) ≤ δ(B^d) ≤ [V(B^d)/(2V(B^(d−1)))]ρ_s(d)^(1−d),

wobei V(B^d) das Volumen des Einheitsballs in d Dimensionen ist. Für d = 2 sind beide Parameter gleich; dies wird für alle d vermutet. Bei einer dichtesten Gitterpackung hängt für ρ ≥ ρ_c(d) das normierte Polytop (1/n^d)C_(n,ρ) im Grenzfall n → ∞ nur von ρ und dem Gitter L ab und entspricht der Wulff-Konstruktion von Kristallen.

Kreispackungen in Containern

Auch endliche Packungen kongruenter Kreise in vorgegebenen Behältern wurden untersucht, etwa auf Kugeloberflächen oder in Quadraten. Dichteste symmetriefreie Packungen von n kongruenten Kreisen in Quadraten konnten für n > 10 nur mit Computerhilfe gefunden werden. Grundlegend für Optimalitätsbeweise war die Arbeit eines Teams um Ronald Peikert an der ETH Zürich.

Für n = 10 gibt es im Einheitsquadrat bis auf Kongruenz genau eine dichteste Packung. Sie ist symmetriefrei und wurde 1976 von K. Schlüter-Schmidtke ohne Computerhilfe gefunden.