Benutzer:Pizzaschneider/Kreispackung

Beispiel für eine Kreispackung in der Ebene

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

Ein planarer Graph und die dazugehörige Kreispackung

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 KAT-Theorem (unten) 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.

Theoreme

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, dessen 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. Thursten entdeckte es 1978 wieder und bemerkte, dass es bereits aus Ergebnissen von Andreev folgte.

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?".

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\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 bzw. Stephenson.

Anwendungen

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.

Origami

In 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.

Literatur

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