Kreispackung

In der Mathematik ist eine Kreispackung eine Ansammlung von Kreisen in der euklidischen Ebene bzw. auf einer beliebigen Fläche. Kreispackungen werden hinsichtlich ihrer Adjazenzen und ihrer Geometrie untersucht und spielen eine Rolle in den mathematischen Bereichen der Graphentheorie und der Funktionentheorie.

Anschaulich ähnlich, von der Theorie aber ein eigenes Gebiet, ist das Thema der Kugelpackungen.

Begriffe

Wir bezeichnen eine Menge von Kreisscheiben in der euklidischen Ebene als Kreispackung, falls die Kreisscheiben sich paarweise in höchstens einem Punkt schneiden. Ein Graph $G=(V,E)$ ist eine Menge von Knoten $V$ und Kanten $E$ zwischen den Knoten. Der Kontaktgraph einer Kreispackung entsteht aus folgender Konstruktion: Der Graph enthält für jeden Kreis einen Knoten. Zwei Knoten sind mit einer Kante verbunden, falls sich die beiden Kreise in der Ebene berühren. Zwei Graphen heißen isomorph, falls wir eine Eins-zu-Eins-Beziehung zwischen den beiden Graphen finden, sodass Nachbarschaften erhalten bleiben.

Die zentrale Frage in der Theorie der Kreispackungen lautet nun: „Gibt es für einen gegebenen Graphen $G$ eine Kreispackung, dessen Kontaktgraph isomorph zu $G$ ist?“. Das Koebe-Andreev-Thurston-Theorem beantwortet diese Frage: Es gibt genau dann eine solche Kreispackung, wenn $G$ planar ist. Diese Aussage verbindet also die geometrische Anordnung der Kreise mit der Kombinatorik eines Graphen.

Eigenschaften

Koebe-Andreev-Thurston-Theorem

Das Koebe-Andreev-Thurston-Theorem (KAT-Theorem) bzw. „circle packing theorem“ besagt, dass jeder planare Graph $G$ eine Kreispackung in der Ebene besitzt, deren Kontaktgraph isomorph zu $G$ ist.

Das Theorem ist nach den drei Mathematikern Paul Koebe, E. M. Andreev sowie William P. Thurston benannt. Koebe bewies das Theorem 1936, es geriet jedoch in Vergessenheit. Thurston entdeckte es 1978 wieder und bemerkte, dass es bereits aus Ergebnissen von Andreev folgte.^[1]

Eindeutigkeit

Im Laufe der Entwicklung des KAT-Theorems wurde auch die Eindeutigkeit der Kreispackungen untersucht. Von Thurston selbst stammt die Beobachtung: Für einen maximal planaren Graphen gibt es bis auf Möbiustransformationen in der Ebene nur genau eine korrespondierende Kreispackung. Besitzt ein Graph also zwei korrespondierende Kreispackungen, so existiert eine Kombination aus Parallelverschiebung, Drehstreckungen und Inversionen der Ebene, welche die beiden Kreispackungen ineinander überführt.

Mohar bewies die Eindeutigkeit sogar für eine größere Klasse von Graphen, den reduzierten Karten.^[2]

Algorithmen

Neben der Existenz und Eindeutigkeit einer Kreispackung für einen gegebenen Graphen ist eine zentrale Fragestellung die effiziente Berechenbarkeit. Aus Sicht der Komplexitätstheorie ist die exakte Berechnung einer Kreispackung NP-vollständig. Daher kann es unter der Voraussetzung $P\neq NP$ (P-NP-Problem) keinen effizienten Algorithmus zur Berechnung geben. In der Praxis existieren aber mehrere Approximationsalgorithmen, die eine ausreichende Genauigkeit erzielen können. Dazu zählen zum Beispiel Algorithmen von Mohar und Stephenson.^[2]

Optimierungsprobleme

Kreispackungen motivieren Untersuchungen von diversen Optimierungsproblemen. Dazu zählt beispielsweise die nach der dichtesten Kreispackung in einem Kreis, in einem Quadrat oder allgemein in einem Rechteck. Ist eine Menge von Kreisen und ein Rechteck gegeben, dann ist das Entscheidungsproblem, ob eine Packung der Kreise in das Rechteck existiert, NP-vollständig.^[3]

Dichteste Kreispackungen

Dichteste Kreispackung von gleich großen Kreisen in der zweidimensionalen Ebene

Wenn die Kreise gleich groß sind, hat die dichteste Kreispackung für die zweidimensionale Ebene die Packungsdichte

P={\frac {\pi \cdot {\sqrt {3}}}{6}}\approx 0{,}907

Zur Berechnung der Packungsdichte kann folgendermaßen vorgegangen werden: Eine bestimmte Konstellation von Kreissektoren wird mit einem regelmäßigen Sechseck, einem gleichseitigen Dreieck oder mit einer Raute überdeckt, wobei die Ecken der Polygone Mittelpunkte der Kreise sind. Eine andere Möglichkeit ist es, die Kreise als Inkreise von regelmäßigen Sechsecken zu betrachten. Bei diesen Berechnungsmethoden entsteht jeweils eine regelmäßige Parkettierung.

Zu beweisen, dass die Packungsdichte maximal ist, ist weit komplizierter. Entscheidende Beiträge dazu lieferten Joseph Louis Lagrange im Jahr 1773 und Axel Thue im Jahr 1890.^[4]^[5] Der allgemeine Fall ohne Gitterstruktur wurde im Jahr 1942 von László Fejes Tóth bewiesen.^[6]

Dichteste Kreispackung von gleich großen Kreisen in einem Kreis

Die Fragestellung, wie viele Kreise gleicher Größe in einen größeren Kreis hineinpassen, hat sich als noch komplizierter erwiesen. Das liegt unter anderem daran, dass die Anordnung der Kreise für die dichteste Kreispackung fast immer unregelmäßig ist und dass die Anordnung mit Kreisen, die neu hinzukommen, im Allgemeinen komplizierter wird. Es wurden weitere ähnliche Fragestellungen für Flächen endlicher Größe untersucht, zum Beispiel, wie viele Kreise gleicher Größe in ein größeres Quadrat hineinpassen.

Kreispackungen in geometrischen Formen

Steiner-Kette

Eine Steiner-Kette ist in eine zusammenhängende Folge endlich vieler, einander berührender Kreise, von denen jeder außerdem zwei vorgegebene, sich nicht schneidende Kreise, die sogenannten Ausgangskreise, berührt. Eine Steiner-Kette bildet zusammen mit dem inneren Ausgangskreis genau dann eine Kreispackung im äußeren Ausgangskreis, wenn sie geschlossen ist.

Eine fundamentale Aussage über die Steiner-Kette ist der Steinersche Kreiskettensatz (auch Schließungssatz von Steiner):

Wenn zwischen zwei Ausgangskreisen mindestens eine geschlossene Steiner-Kette möglich ist, dann sind auch unendlich viele möglich, wobei jeder beliebige Kreis, der die beiden Ausgangskreise berührt, der Startkreis einer solchen Kette sein kann.

Dies bedeutet, dass jede dieser Ketten durch "Rotation" der ursprünglichen Kette entlang der Ausgangskreise aus der Ursprungskette hervorgehen kann.

Pappos-Kette

Eine Pappos-Kette ist eine unendliche Folge einander berührender Kreise in einem Arbelos. Das Arbelos ist eine von drei Halbkreisen begrenzte geometrische Figur. Wird eine Pappos-Kette am Durchmesser des äußerem Halbkreises gespiegelt, dann entsteht eine unendliche Kreispackung mit einem äußeren Kreis. Diese unendliche Kreispackung kann in eine endliche Kreispackung umgewandelt werden, indem nur die ersten Kreise der unendliche Folge verwendet werden.

Apollonios-Kreisfüllung

Die apollonische Kreispackung ist eine Kreispackung, bei der in das Kreisbogendreieck zwischen drei sich paarweise berührenden Kreisen ein weiterer möglichst großer Kreis eingeschrieben und dieser Vorgang rekursiv fortgesetzt wird. Die Apollinios-Kreisfüllung ist eines der ersten jemals beschriebenen Fraktale. Es gibt Apollonios-Kreisfüllungen, in denen die Kehrwerte der Radien aller Kreise ganzzahlig sind wie im Bild. Auf diese Weise entsteht eine Verbindung zur Gruppen- und Zahlentheorie.

Malfatti-Kreise

Die Malfatti-Kreise füllen das Innere eines Dreiecks so aus, dass sie jeweils eine Seite des Dreiecks und die beiden anderen Kreise tangential berühren. Der Mathematiker Gianfrancesco Malfatti nahm 1803 fälschlich an, dass diese Konstruktion die maximale Bedeckung des Dreiecks durch drei Kreise sei.

Verallgemeinerungen

Man muss sich nicht auf die Betrachtung von (disjunkten) Kreispackungen von Kreisen in der Ebene beschränken. In der mathematischen Forschung werden verschiedene weiterführende Fragestellungen betrachtet. Dazu gehört die Frage, ob es für einen gegebenen Graphen eine korrespondierende Kreispackung auf einer anderen Fläche als der euklidischen Ebene, also z. B. in der projektiven Ebene oder auf einer hyperbolischen Fläche gibt. Eine andere Fragestellung entsteht, wenn die euklidische Metrik durch eine andere ersetzt wird.^[7]

Anwendungen

Die Theorie der Kreispackungen findet innerhalb der Mathematik in diversen Bereichen Anwendung. Dazu zählt die Berechnung optimaler Schranken für das Separator-Problem in der Graphentheorie^[8] oder die Darstellung von algebraischen Gruppen.

Des Weiteren kann die Berechnung von Kreispackungen im Bereich des Graphzeichnens verwendet werden, um automatisierte Einbettungen von planaren Graphen zu erstellen. Die Existenz einer kreuzungsfreien Einbettung für einen Graphen kann kombinatorisch effizient durch einen Planaritätstest nachgewiesen werden. Eine tatsächliche Einbettung unter Einhaltung ästhetischer Anforderungen ist dennoch anspruchsvoll zu konstruieren.

Gehirn-Scans

Kreispackungen werden zur Approximation von analytischen Funktionen eingesetzt und beschreiben konforme Abbildungen. In der Medizintechnik werden diese Funktionen eingesetzt, um aus dreidimensionalen Daten aus den bildgebenden Verfahren eine zweidimensionale Repräsentation zu berechnen, die leichter zu analysieren ist. Dabei helfen die Kreispackungen lokale Strukturen zu erhalten.^[9]

Origami

In der mathematischen Disziplin des Origami war lange die Frage offen, welche dreidimensionalen Figuren aus einem Blatt Papier ohne Schnitte gefaltet werden können und ob es einen Algorithmus gibt, der eine Faltanleitung für beliebige Figuren angeben kann. In den 1980er Jahren wurde diese Frage positiv durch Robert E. Lang und Toshiyuki Meguro gemeinsam beantwortet. Die Berechnung eines solchen Faltmusters verwendet Kreispackungen. Jedem disjunkten Kreis entspricht eine „Extremität“ des zu faltenden Objekts. Miteinander verbundene Teile des Objekts sind durch die Adjazenzen im Graph der Kreise charakterisiert.

Die Origami-Faltmuster werden sowohl in der Kunst als auch in wissenschaftlichen und wirtschaftlichen Anwendungen verwendet. Dazu zählen optimale Faltungen für Satelliten und Airbags.^[10]

Literatur

Kenneth Stephenson: Introduction to Circle Packing: The Theory of Discrete Analytic Functions. Cambridge University Press, 2005.

Einzelnachweise

↑ William P. Thurston: The geometry and topology of three-manifolds. 1978.
↑ ^a ^b Bojan Mohar: A polynomial time circle packing algorithm. Elsevier, 1993, S. 257–263.
↑ Demaine, Fekete, Lang: Circle Packing for Origami Design Is Hard. 2010.
↑ Max Leppmeier, Universität Bayreuth: A Simple Proof of Thue’s Theorem on Circle Packing and an elementary proof of Thue ́s theorem
↑ Hai-Chau Chang, Lih-Chung Wang, National Taiwan University, National Donghwa University: A Simple Proof of Thue’s Theorem on Circle Packing
↑ SpringerLink, L. Fejes: Über die dichteste Kugellagerung
↑ Bojan Mohar: Drawing Graphs in the Hyperbolic Plane. 1999, ISBN 978-3-540-46648-2, S. 127–136.
↑ Miller, Teng, Thurston, Vavasis: Separators for sphere-packings and nearest neighbor graphs. 1997.
↑ Charles R. Collins and Kenneth Stephenson: A circle packing algorithm. 2003.
↑ Robert J. Lang: Mathematical Methods in Origami Design. 2009.

[1] William P. Thurston: The geometry and topology of three-manifolds. 1978.

[Mohar-S257-263-2] Bojan Mohar: A polynomial time circle packing algorithm. Elsevier, 1993, S. 257–263.

[3] Demaine, Fekete, Lang: Circle Packing for Origami Design Is Hard. 2010.

[4] Max Leppmeier, Universität Bayreuth: A Simple Proof of Thue’s Theorem on Circle Packing and an elementary proof of Thue ́s theorem

[5] Hai-Chau Chang, Lih-Chung Wang, National Taiwan University, National Donghwa University: A Simple Proof of Thue’s Theorem on Circle Packing

[6] SpringerLink, L. Fejes: Über die dichteste Kugellagerung

[7] Bojan Mohar: Drawing Graphs in the Hyperbolic Plane. 1999, ISBN 978-3-540-46648-2, S. 127–136.

[8] Miller, Teng, Thurston, Vavasis: Separators for sphere-packings and nearest neighbor graphs. 1997.

[9] Charles R. Collins and Kenneth Stephenson: A circle packing algorithm. 2003.

[10] Robert J. Lang: Mathematical Methods in Origami Design. 2009.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Kreispackung

Inhaltsverzeichnis

Begriffe