Kreispackung

Grundidee und zentrale Begriffe

Eine Kreispackung ist eine Ansammlung von Kreisen in der euklidischen Ebene oder auf einer anderen Fläche. Genauer bezeichnet man eine Menge von Kreisscheiben als Kreispackung, wenn sich die Kreisscheiben paarweise höchstens in einem Punkt berühren und nicht überlappen. Untersucht werden sowohl die geometrische Anordnung als auch die Berührungsbeziehungen zwischen den Kreisen. Kreispackungen sind besonders für die Graphentheorie und die Funktionentheorie wichtig. Kugelpackungen sehen ähnlich aus, bilden theoretisch aber ein eigenes Gebiet.

Ein Graph G = (V, E) besteht aus einer Knotenmenge V und Kanten E zwischen den Knoten. Der Kontaktgraph einer Kreispackung besitzt für jeden Kreis einen Knoten; zwei Knoten werden genau dann durch eine Kante verbunden, wenn sich die zugehörigen Kreise berühren. Zwei Graphen heißen isomorph, wenn zwischen ihren Knoten eine Eins-zu-eins-Zuordnung besteht, die alle Nachbarschaften erhält.

Die zentrale Frage lautet, ob zu einem gegebenen Graphen G eine Kreispackung existiert, deren Kontaktgraph isomorph zu G ist. Damit wird die geometrische Anordnung von Kreisen mit der kombinatorischen Struktur eines Graphen verbunden.

Existenz, Eindeutigkeit und Berechnung

Das Koebe-Andreev-Thurston-Theorem, kurz KAT-Theorem oder „circle packing theorem“, beantwortet die Existenzfrage: Jeder planare Graph G besitzt eine Kreispackung in der Ebene, deren Kontaktgraph isomorph zu G ist. Ein planarer Graph ist ein Graph, der ohne sich kreuzende Kanten in der Ebene gezeichnet werden kann. Paul Koebe bewies das Theorem 1936; William P. Thurston entdeckte es 1978 wieder und stellte fest, dass es bereits aus Ergebnissen von E. M. Andreev folgte.

Für maximal planare Graphen ist die zugehörige Kreispackung bis auf Möbiustransformationen eindeutig. Das bedeutet: Gibt es zwei entsprechende Packungen, lassen sie sich durch eine Kombination aus Parallelverschiebungen, Drehstreckungen und Inversionen der Ebene ineinander überführen. Mohar bewies eine entsprechende Eindeutigkeit für die größere Klasse der reduzierten Karten.

Neben Existenz und Eindeutigkeit ist die Berechenbarkeit wichtig. Die exakte Berechnung einer Kreispackung ist NP-vollständig. Unter der Voraussetzung P ≠ NP kann es daher keinen effizienten Algorithmus für alle Fälle geben. In der Praxis liefern jedoch Approximationsalgorithmen, etwa von Mohar und Stephenson, ausreichend genaue Näherungen.

Auch viele Packungsfragen sind Optimierungsprobleme: Gesucht wird beispielsweise die dichteste Kreispackung in einem Kreis, Quadrat oder Rechteck. Sind eine Menge von Kreisen und ein Rechteck gegeben, ist bereits die Entscheidung, ob die Kreise in das Rechteck gepackt werden können, NP-vollständig.

Dichteste Packungen

Für gleich große Kreise in der gesamten zweidimensionalen Ebene ist die hexagonale Anordnung am dichtesten. Ihre Packungsdichte, also der von den Kreisen bedeckte Flächenanteil, beträgt

P = (π · √3) / 6 ≈ 0,907.

Die Dichte lässt sich mithilfe eines regelmäßigen Sechsecks, eines gleichseitigen Dreiecks oder einer Raute berechnen, deren Ecken Kreismittelpunkte sind. Alternativ kann man die Kreise als Inkreise regelmäßiger Sechsecke betrachten. In allen Fällen entsteht eine regelmäßige Parkettierung. Der Nachweis, dass keine andere Anordnung dichter ist, ist wesentlich schwieriger. Joseph Louis Lagrange lieferte 1773 und Axel Thue 1890 entscheidende Beiträge; den allgemeinen Fall ohne vorausgesetzte Gitterstruktur bewies László Fejes Tóth 1942.

Schwieriger ist die Frage, wie viele gleich große kleine Kreise in einen größeren Kreis passen. Optimale Anordnungen sind fast immer unregelmäßig und verändern sich beim Hinzufügen weiterer Kreise im Allgemeinen auf komplizierte Weise. Vergleichbare Untersuchungen betreffen etwa die größtmögliche Zahl gleich großer Kreise in einem Quadrat.

Besondere Kreispackungen und geometrische Formen

Eine Steiner-Kette ist eine zusammenhängende endliche Folge einander berührender Kreise. Jeder dieser Kreise berührt außerdem zwei vorgegebene, einander nicht schneidende Ausgangskreise. Zusammen mit dem inneren Ausgangskreis bildet die Kette genau dann eine Kreispackung im äußeren Ausgangskreis, wenn sie geschlossen ist. Der Steinersche Kreiskettensatz besagt: Ist zwischen zwei Ausgangskreisen mindestens eine geschlossene Steiner-Kette möglich, dann gibt es unendlich viele. Jeder beliebige Kreis, der beide Ausgangskreise berührt, kann als Startkreis dienen; anschaulich gehen die Ketten durch eine „Rotation“ entlang der Ausgangskreise auseinander hervor.

Eine Pappos-Kette ist eine unendliche Folge sich berührender Kreise in einem Arbelos, einer von drei Halbkreisen begrenzten Figur. Spiegelt man sie am Durchmesser des äußeren Halbkreises, entsteht eine unendliche Kreispackung mit einem äußeren Kreis. Durch Beschränkung auf die ersten Glieder der Folge erhält man eine endliche Packung.

Bei einer apollonischen Kreispackung wird in das Kreisbogendreieck zwischen drei paarweise einander berührenden Kreisen ein weiterer möglichst großer Kreis eingeschrieben. Dieser Vorgang wird rekursiv wiederholt. Die Apollonios-Kreisfüllung gehört zu den ersten beschriebenen Fraktalen. In manchen dieser Füllungen sind die Kehrwerte sämtlicher Kreisradien ganzzahlig; dadurch besteht eine Verbindung zur Gruppen- und Zahlentheorie.

Die drei Malfatti-Kreise liegen in einem Dreieck. Jeder Kreis berührt eine Dreiecksseite und die beiden anderen Kreise tangential. Gianfrancesco Malfatti nahm 1803 irrtümlich an, diese Anordnung liefere die maximale Bedeckung eines Dreiecks durch drei Kreise.

Hexagonale Strukturen und Goldener Schnitt

In einer hexagonalen Kreispackung der Ebene berührt jeder nicht überlappende Kreis genau sechs andere Kreise. Für solche Packungen ist das Verhältnis zwischen dem kleinsten und dem größten auftretenden Radius entweder 1, wenn alle Kreise gleich groß sind, oder andernfalls 0. Die Kreismittelpunkte liegen auf logarithmischen Spiralen, Kreisen oder Geraden. Die Radien der auf diese Weise verbundenen Kreise besitzen stets dasselbe Verhältnis und bilden daher eine geometrische Folge.

Bestimmte Packungen aus fünf Kreisen in einem Rechteck stehen mit dem Goldenen Schnitt in Beziehung. Dabei sei a der Radius eines grünen Kreises, zwei rote Kreise hätten jeweils den Radius 1, zwei blaue jeweils den Radius b, und c sei der Abstand zwischen dem Mittelpunkt des linken roten und des oberen blauen Kreises. Es gilt das nichtlineare Gleichungssystem

a + 2b = 1, c = a + 1, c² + (a + b)² = (1 + b)².

Seine Lösung lautet

a = √5 − 2, b = (3 − √5) / 2, c = √5 − 1.

Daraus ergeben sich drei Goldene Rechtecke, also Rechtecke mit dem Seitenverhältnis Φ: Das erste hat die Seitenlängen 2 und c mit 2/c = Φ. Das zweite besitzt die Seiten c und 2b mit c/(2b) = Φ. Beim dritten sind die Seiten 2a + 2b und 2b lang; auch hier gilt (2a + 2b)/(2b) = Φ.

Verallgemeinerungen und Anwendungen

Kreispackungen müssen nicht auf disjunkte Kreise in der euklidischen Ebene beschränkt bleiben. Untersucht werden auch Packungen auf anderen Flächen, etwa in der projektiven Ebene oder auf einer hyperbolischen Fläche, sowie Packungsprobleme, bei denen die euklidische Metrik durch eine andere Metrik ersetzt wird.

Innerhalb der Mathematik dienen Kreispackungen unter anderem zur Berechnung optimaler Schranken für das Separator-Problem der Graphentheorie und zur Darstellung algebraischer Gruppen. Beim automatischen Graphzeichnen helfen sie, planare Graphen geometrisch einzubetten. Zwar lässt sich mit einem Planaritätstest kombinatorisch effizient feststellen, ob eine kreuzungsfreie Einbettung existiert; eine konkrete Einbettung, die zusätzlich ästhetische Anforderungen erfüllt, bleibt jedoch schwierig.

Kreispackungen approximieren analytische Funktionen und beschreiben konforme Abbildungen, also winkeltreue Abbildungen. In der Medizintechnik werden solche Abbildungen verwendet, um aus dreidimensionalen Daten bildgebender Verfahren eine leichter analysierbare zweidimensionale Darstellung zu berechnen. Dabei tragen Kreispackungen dazu bei, lokale Strukturen zu erhalten.

Auch mathematisches Origami nutzt Kreispackungen. Robert E. Lang und Toshiyuki Meguro beantworteten in den 1980er Jahren positiv die Frage, ob sich Faltanleitungen für beliebige dreidimensionale Figuren ohne Schnitte algorithmisch bestimmen lassen. Bei der Berechnung eines Faltmusters entspricht jeder disjunkte Kreis einer „Extremität“ des zu faltenden Objekts; die Adjazenzen im Kontaktgraphen beschreiben miteinander verbundene Teile. Solche Faltmuster werden in der Kunst sowie für wissenschaftliche und wirtschaftliche Aufgaben eingesetzt, darunter optimale Faltungen von Satelliten und Airbags.