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 ist eine Menge von Knoten und Kanten 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 eine Kreispackung, dessen Kontaktgraph isomorph zu ist?“. Das KAT-Theorem (unten) beantwortet diese Frage: Es gibt genau dann eine solche Kreispackung, wenn 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 eine Kreispackung in der Ebene besitzt, deren Kontaktgraph isomorph zu 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 Translationen, 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]
Optimierungsprobleme
Kreispackungen motivieren Untersuchungen von diversen Optimierungsproblemen. Dazu zählt beispielsweise die nach der optimalen Packung von Kreisen in einem Kreis oder Kreisen in einem Quadrat bzw. allgemein in einem Rechteck. Gegeben eine Menge von Kreisen und ein Rechteck, so ist das Entscheidungsproblem, ob eine Packung der Kreise in das Rechteck existiert, NP-vollständig.[3]
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 zählen beispielsweise folgende: „Gibt 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?“ und „Was passiert, wenn die die euklidische Metrik durch eine andere ersetzt wird?“.[4]
Berechnung
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-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 bzw. Stephenson.[2]
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[5] 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.[6]
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 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.[7]
Siehe auch
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.
- Bojan Mohar: A polynomial time circle packing algorithm. Elsevier, 1993, S. 257–263.
- Demaine, Fekete, Lang: Circle Packing for Origami Design Is Hard. 2010.
- 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.