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.
Begriffe
Bearbeiten
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.
Theoreme
BearbeitenKoebe-Andreev-Thurston-Theorem
BearbeitenDas Koebe-Andreev-Thurston-Theorem (KAT-Theorem) bzw. 'circle packing theorem' besagt, dass jeder planare Graph eine Kreispackung in der Ebene besitzt, dessen 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. Thursten entdeckte es 1978 wieder und bemerkte, dass es bereits aus Ergebnissen von Andreev folgte. [1]
Verallgemeinerungen
BearbeitenMan 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?". [2]
Berechnung
BearbeitenNeben 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.[3]
Anwendungen
BearbeitenGehirn-Scans
BearbeitenKreispackungen 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.[4]
Origami
BearbeitenIn der mathematischen Disziplin des Origami war lange die Frage offen, welche dreidimensionalen Figuren aus einem Blatt Papier ohne Schnitte gefaltet werden kann 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 Objektes. Miteinander verbundene Teile des Objektes 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.[5]
Literatur
Bearbeiten- Kenneth Stephenson: Introduction to Circle Packing: The Theory of Discrete Analytic Functions. Cambridge University Press, 2005.
Weblinks
Bearbeiten- ↑ William P. Thurston: The geometry and topology of three-manifolds. 1978.
- ↑ Bojan Mohar: Drawing Graphs in the Hyperbolic Plane. 1999, ISBN 978-3-540-46648-2, S. 127–136.
- ↑ Bojan Mohar: A polynomial time circle packing algorithm. Elsevier, 1993, S. 257–263.
- ↑ Charles R. Collins and Kenneth Stephenson: A circle packing algorithm. 2003.
- ↑ Robert J. Lang: Mathematical Methods in Origami Design. 2009.