Theorie der endlichen Kugelpackungen

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

[[Hilfe:Cache|Fehler beim Thumbnail-Erstellen]]:

Konvexe Hülle, blau eingefärbt

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.

• Kugelwurst.svg

  Wurstpackung

• SetUpofTriangleForStandardPool.jpg

  Pizzapackung

• Kugelcluster.svg

  Clusterpackung

Wurstpackung

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öhrenkarton. Tatsächlich müssten die beiden Enden der Verpackung abgerundet sein, was in der Realität aber meist nicht der Fall ist.

Pizzapackung

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 oder die Kugelpackung in Dreiecken, die für den Aufbau von Billard-Kugeln verwendet werden. Das gilt für Packungen in euklidischen Räumen mit drei Dimensionen.

Clusterpackung

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 und Lagen angeordnet wird.

Zusammenhänge

Nach dieser Definition ist eine Wurstpackung auch immer eine Pizzapackung und eine Pizzapackung auch immer eine Clusterpackung. Im allgemeinen Fall von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} Dimensionen spricht man bei eindimensionaler Anordnung von Wurst, bei d-dimensionaler Anordnung von Cluster und für die dazwischenliegenden Dimensionen von Pizza.

Eine oder zwei Kugeln bilden immer eine Wurstpackung. 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.

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

Clusterpackung von 56 Kugeln (dichter)

Bei drei und vier Kugeln ist die optimale Packung eine Wurstpackung. Man vermutet, dass dies bis zu einer Anzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} von $55$ sowie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=57, 58, 63 \text{ und } 64} Kugeln gilt. Bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 $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 $d=4$ Dimensionen wird ein sprunghafter Übergang von optimaler Wurstform zu Cluster spätestens bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 375.370} Kugeln vermutet.

Für Kugelpackungen in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d \geq 3} konvexe Körper, für die die Pizza die dichteste Packung ist (Peter Gritzmann, Arhelger).

Beispiel für den Nachweis, dass eine Wurstpackung nicht optimal ist

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

Das Volumen der konvexen Hülle einer Wurstpackung aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Kugeln mit dem Radius Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} lässt sich aus elementaren geometrischen Körpern berechnen. Die Hülle besteht in der Mitte aus einem Zylinder der Höhe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h = 2r \cdot (n-1)} und an den beiden Enden aus je einer Halbkugel mit dem Radius $r$. Das Volumen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V_W} der konvexen Hülle berechnet sich deshalb nach der folgenden Formel.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} V_W &= V_\text{Zylinder} + 2 \cdot V_\text{Halbkugel}\\ &= V_\text{Zylinder} + V_\text{Kugel}\\ &= \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}}

Ä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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} Kugeln, so berechnet sich die Gesamtzahl der aufgeschichteten Kugeln $n$ durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} eines Tetraeders mit Kantenlänge $a$ ist

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r = \frac{\sqrt{6}}{12} \cdot a} .

Dies lässt sich nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} umstellen

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

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} des Tetraeders pro Schicht um das Doppelte des Kugelradius, das heißt, bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} Schichten ergibt sich eine Kantenlänge von

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V} der konvexen Hülle der aufgeschichteten Kugeln die Abschätzung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V < \frac{2 \cdot \left( x - 1 + \sqrt{6} \right)^3 \cdot \sqrt{2} \cdot r^3}{3}} .

Setzt man nun die Formel für die Anzahl der Kugeln bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Schichten in die Formel für das Volumen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V_\text{W}} der Hülle einer Wurstpackung ein, erhält man das von der Wurstpackung eingenommene Volumen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V_\text{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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x = 13} , also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Wurstpackung größer als 2856 ist. Dies beweist, dass für 455 Kugeln die Tetraederpackung dichter als die Wurstpackung ist.

Mit etwas mehr Aufwand lässt sich statt der Abschätzung für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} und damit kleinere zugehörige Kugelzahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} den Nachweis zu, dass die Wurstpackung nicht die optimale Packung darstellt.

Wurstvermutung

Die Bezeichnung Wurst stammt vom Mathematiker László Fejes Tóth, der 1975 die Wurstvermutung aufstellte. Die optimale Anordnung von Kugeln kann man in beliebigen Dimensionen untersuchen. Kugeln, konvexe Hüllen sowie Volumina können in jedem euklidischen Raum mit mehr als einer Dimension formuliert werden. Der verallgemeinerte Begriff der Kugel bezeichnet dann einen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} -dimensionalen Körper, bei dem alle Randpunkte gleich weit von seinem Mittelpunkt entfernt sind, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} die jeweilige Anzahl der Raumdimensionen bezeichnet. Die Wurstvermutung von Fejes Tóth besagt, dass ab einer Dimension von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 5} die Anordnung von Kugeln entlang einer Geraden immer die Beste ist. Demnach würde die Wurstkatastrophe in einem Raum mit mehr als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 4} Dimensionen nicht mehr auftreten. Ob dies tatsächlich stimmt, ist noch unbewiesen. Das beste Resultat hierzu stammt von Ulrich Betke und Martin Henk. Sie bewiesen 1998, dass ab einer Dimension von $42$ die Wurstvermutung tatsächlich gilt. Ab dem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 42} -dimensionalen Raum ist die Wurst also immer die dichteste Anordnung, und die Wurstkatastrophe tritt nicht ein. Im zweidimensionalen Raum ist nach J. M. Wills die optimale Anordnung immer ein Cluster.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} -dimensionalen Cluster angeordnet.

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) Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} :

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta (K, C_n) =\frac {n V(K)}{V (C_n +K)}}

mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C_n} der konvexen Hülle der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Schwerpunkte Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle c_{i}} der Kugeln $K_{i}$ (hier werden Kugeln betrachtet, man kann aber auch andere konvexe Körper Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta =1} (Endliche Anordnung). Raumfüllend (unendliche Anordnung) ist aber eine hexagonale Anordnung mit einer Dichte von etwa Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0{,}9} . Einen Ausweg bietet eine modifizierte Definition der Dichte nach Wills mit einem positiven Parameter $\rho$:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \delta (K,C_{n})={\frac {nV(K)}{V(C_{n}+\rho K)}}}

Mit dem Parameter Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d \geq 2} gibt es Parameterwerte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rho_s (d)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rho_c (d)} , so dass für $\rho \leq \rho _{s}(d)$ die Wurst die dichteste Anordnung ist (für alle Anzahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} ) und für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rho \geq \rho_c (d)} und für hinreichend große Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Cluster die dichteste Anordnung sind. Die Parameterwerte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rho_s (d)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rho_c (d)} sind jeweils dimensionsspezifisch. In zwei Dimensionen ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac {V (B^d)}{2 V (B^{d-1})} {\rho_c (d)}^{1-d} \leq \delta (B^d) \leq \frac {V (B^d)}{2 V (B^{d-1})} {\rho_s (d)}^{1-d} }

mit dem Volumen des Einheitsballs $B^{d}$ in $d$ Dimensionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V (B^d)} . Für $d=2$ ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rho_s (d) =\rho_c (d)} und es wird vermutet, dass das für alle Dimensionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} gilt. Aus der Bestimmung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta (B^d) } folgt dann der Wert von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rho_c (d)} .

Betrachtet man eine dichteste Gitterpackung (Gitter L) von Kugeln $C_{n,\rho }+\rho B^{d}$, so ist für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rho \geq \rho_c (d)} so hängt das normierte Polytop Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac {1}{n^d} C_{n, \rho}} im Grenzfall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \to \infty} nur von $\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} kongruenten Kreisen in Quadraten konnten für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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