Es gibt ein Partyspiel namens "Sardinen", bei dem es darum geht, möglichst viele Leute in einen Kleiderschrank zu packen. Mathematiker haben ein ähnliches Spiel; da sie sich aber mit den Körperformen von Fischen oder Menschen nicht im einzelnen auseinandersetzen mögen – zumindest nicht beruflich –, spielen sie lieber mit Kreisen. Wie groß ist der kleinste quadratische Kasten, in den man 49 Milchflaschen aufrecht stehend packen kann? Oder, wissenschaftlicher ausgedrückt: Wie groß darf der Radius eines Kreises höchstens sein, wenn 49 Exemplare davon ohne Überlappung in ein Einheitsquadrat passen sollen? Kekse auf ein quadratisches Kuchenblech, runde Menschen in einen quadratischen Kleiderschrank – in der Abstraktion ist das alles dasselbe.

Daß diese beiden Probleme äquivalent sind, ist leicht einzusehen: Eine Lösung des einen liefert nach einer einfachen Skalierung eine Lösung des anderen. Vorausgesetzt natürlich, daß man keine Flasche auf den Kopf stellt oder auf die Seite legt.

Solche Packungsprobleme mit äußerer Begrenzung gehören zu dem jungen und erstaunlich schwierigen Gebiet der kombinatorischen Geometrie. Fast alles, was man darüber weiß, stammt aus dem Jahre 1960 oder aus späterer Zeit.

Ein quadratischer Kasten, in den man 49 Milchflaschen vom Durchmesser 1 packen kann, müßte die Seitenlänge 7 haben: Man stellt einfach 7×7 Flaschen zeilen- und spaltenweise in Reih und Glied. Einleuchtend – aber falsch. Kari J. Nurmela und Patric R. J. Östergård von der Technischen Universität Helsinki fanden 1997 eine Möglichkeit, 49 Kreise in ein etwas kleineres Quadrat zu packen. Der deutsche Mathematiker Gerhard Wengerodt hatte zuvor gezeigt, daß die Quadratpackung für 1, 4, 9, 16, 25 und 36 Kreise optimal ist, nicht aber für 64, 81 und alle größeren Quadratzahlen.

Je größer die Anzahl der Kreise, desto eher neigt ihre optimale Anordnung dazu, vom Quadratgitter abzuweichen. Denn in der unendlich ausgedehnten Ebene ist eine andere Packung die dichteste: die hexagonale, bei der jeder Kreis von sechs anderen umgeben ist. Eine quadratische Begrenzung paßt nicht zu einer hexagonalen Packung; es würden große Lücken bleiben. Deshalb ist bei kleinen Anzahlen von Kreisen die Quadratgitter-Packung optimal. Je mehr Kreise es werden, desto mehr läßt die Wirkung des Randes nach, so daß Lösungen, die einer hexagonalen Packung nahe kommen, besser sind. Packungsprobleme für begrenzte Gebiete sind etwas anderes als für die gesamte Ebene.

Kürzlich erhielt ich eine Arbeit mit dem Titel "Packen und Überdecken mit Kreisen", mit der Hans Melissen im Dezember 1997 an der Universität Utrecht (Niederlande) promoviert hat. Sie enthält die nach meiner Kenntnis beste und vollständigste Untersuchung solcher Fragen.

Über die Aufgabe, eine gegebene Anzahl gleicher Kreise in ein festes Quadrat zu packen und dabei den Kreisradius zu maximieren, scheint zuerst 1960 etwas gedruckt worden zu sein. Zu dieser Zeit vermutete Leo Moser eine Lösung für acht Kreise. Diese Vermutung wurde kurze Zeit später bestätigt und löste weitere Veröffentlichungen zu verschiedenen Anzahlen von Kreisen aus. Jonathan Schaer, damals an der Universität von Alberta (Kanada) und einer derjenigen, die Mosers Vermutung bewiesen hatten, publizierte 1965 Lösungen für bis zu neun Kreise. Er merkte an, daß Lösungen für bis zu fünf Kreise leicht zu finden seien, und schrieb die Lösung für sechs Kreise Ronald Graham zu, der jetzt bei den Bell-Laboratorien von Lucent Technologies arbeitet.

Die Mathematiker formulieren das Problem meist so um, daß die Kreise selbst gar nicht mehr auftauchen. Wenn zwei gleiche Kreise einander berühren, ist die Entfernung zwischen ihren Mittelpunkten gleich dem Kreisdurchmesser. Und wenn ein Kreis eine gerade Grenzlinie berührt, liegt sein Mittelpunkt auf einer Parallelen zu der Grenzlinie, die von dieser um einen Kreisradius entfernt ist. Wenn wir die Kreise durch deren Mittelpunkte repräsentieren, läßt sich das Problem also folgendermaßen formulieren: "Lege 49 Punkte (Mittelpunkte) so in ein gegebenes Quadrat, daß die minimale Entfernung zwischen irgendzwei dieser Punkte möglichst groß wird." Der Durchmesser der Kreise ist dann diese Minimalentfernung. Aber das Quadrat ist nicht das Originalquadrat, sondern ein kleineres, dessen Seiten um den Betrag des Radius nach innen verschoben sind.

Der Vorteil dieser Formulierung liegt in ihrer größeren Einfachheit. Optimale Anordnungen für bis zu 15 Punkte finden Sie im linken Bild.

Schwieriger ist die Aufgabe, Kreise (oder eben Punkte) in einen großen Kreis zu packen. Die erste bekannte Veröffentlichung zu dieser Frage ist die Doktorarbeit von Boele L. J. Braaksma von der Universität Groningen aus dem Jahre 1963, die eigentlich von einer technischen Frage aus der Analysis handelt. Im Zuge seiner Untersuchungen vermutete Braaksma eine optimale Anordnung von acht Punkten. Später fand er einen Beweis, den er aber nie veröffentlichte. Für bis zu elf Kreise sind heute optimale Lösungen bekannt. Für 12 bis 20 Kreise gibt es Vermutungen, aber bislang stehen Beweise dazu aus (rechtes Bild).

Der erste Beweis für 11 Punkte stammt von Melissen. Er zerlegt zunächst die Kreisfläche in merkwürdig geformte Gebiete, schätzt dann gewisse Abstände ab und gewinnt daraus die Aussage, daß einige dieser Gebiete höchstens einen der zu plazierenden Punkte enthalten können. Auf diese Weise gewinnt er immer präzisere Aussagen über die Verteilung der Punkte und kann schließlich zeigen, daß acht der Punkte auf dem Rand des umgebenden Kreises liegen müssen. Die Methode ist raffiniert und setzt eine geschickte Wahl der Zerlegung voraus. Dennoch ist sie so allgemein, daß sie sich, geeignet modifiziert, auch auf andere derartige Probleme anwenden läßt, oft mit zusätzlicher Unterstützung durch Computerprogramme.

Packungen innerhalb eines gleichseitigen Dreiecks sind besonders interessant, weil diese Form gut zur hexagonalen Packung paßt. Beim Pool-Billard hat der Rahmen aus Holz oder Kunststoff, in den die Bälle anfänglich einsortiert werden, die Form eines gleichseitigen Dreiecks, und die Bälle liegen darin in einem hexagonalen Gitter. Solche Packungen wurden zuerst nur für solche Fälle untersucht, in denen die Anzahl der Kreise eine Dreieckszahl ist, das heißt von der Form 1+2+3+...+n. In diesem Falle ist es einfach: 1, 3, 6, 10, 15 ... Kreise lassen sich als Teil eines perfekten hexagonalen Gitters anordnen.

Über die ganze Ebene gesehen ist die Hexagonalpackung am dichtesten. Das glaubt zwar jeder, aber erst 1892 konnte Axel Thue es auch beweisen. Daher ist höchst plausibel anzunehmen, daß diese Art der Packung innerhalb eines gleichseitigen Dreiecks optimal ist, wenn die Anzahl der zu packenden Kreise eine Dreieckszahl ist. Und es stimmt tatsächlich, aber ein Beweis dafür ist recht trickreich. Melissen gibt einen besonders schönen an. Auch findet er (mit Beweis) optimale Anordnungen für 12 und weniger Punkte und stellt Vermutungen für 16, 17, 18, 19 und 20 Punkte auf (Bild links).

Das Packungsproblem kann man sogar auf gekrümmten Oberflächen stellen. Im Jahre 1930 fragte der niederländische Botaniker Pieter M. L. Tammes nach optimalen Packungen von Kreisen auf der Oberfläche einer Kugel (Spektrum der Wissenschaft, September 1992, Seite 12). Melissen betrachtet eine Variante des Problems von Tammes, bei der die Fläche eine Halbkugel statt einer Kugel ist. Er beweist Resultate für sechs und weniger Punkte, kann aber für 7 bis 15 Punkte nur Vermutungen aufstellen (Bild rechts). R. H. Hardin, N. J. A. Sloane und W. D. Smith haben mit Computerprogrammen mutmaßlich optimale Lösungen für 4 bis 130 Punkte auf der Kugeloberfläche gefunden oder wiederentdeckt, und das gleich in drei- bis fünfdimensionalen Räumen (http://www. research.att.com/~njas/packings/index. html). Ganz ehrgeizige Leser können sich an der Aufgabe versuchen, Kugeln in dreidimensionale Kisten zu packen.

Im Jahre 1985 veröffentlichte die Zeitschrift "Nature" eine kurze Notiz von Alexander A. Berezin von der McMaster-Universität in Ontario. Sie handelte von Konfigurationen minimaler Energie, die geladene Teilchen innerhalb einer Kreisscheibe einnehmen. Das klingt nach Kreispackungsproblem, weil die Teilchen einander abstoßen. Nur kommt es diesmal nicht auf den Abstand selbst an, sondern auf das Kräftegleichgewicht: Das System minimiert seine Gesamtenergie. Wie auch immer, die vorherrschende Meinung war, daß die Teilchen einander an den Rand der Scheibe drücken sollten. Aber Berezins numerische Rechnungen zeigten, daß bei 12 bis 400 Punktladungen die Verteilung mit einer Ladung in der Mitte und dem Rest auf dem Rand eine kleinere Energie hat, als wenn alle Ladungen auf dem Rand säßen.

Die Diskrepanz zwischen der physikalischen Intuition und Berezins Rechnungen konnte schließlich zugunsten der ersteren geklärt werden. Die Lösung niedrigerer Energie ist nicht stabil gegen kleine Verschiebungen der Mittelpunktsladung: Sowie sie ein wenig von ihrer Position abweicht, wird sie gegen den Rand der Scheibe gedrückt.

Das Problem ist aber immer noch interessant. Beispielsweise gibt Melissen den ersten strengen Beweis dafür, daß Berezins numerische Ergebnisse wirklich richtig sind. Trotz aller technischen Schwierigkeiten werden also zur Zeit auf diesem Gebiet allerlei Fortschritte gemacht. Und ich freue mich schon auf weitere.


Aus: Spektrum der Wissenschaft 3 / 1999, Seite 112
© Spektrum der Wissenschaft Verlagsgesellschaft mbH