Hans Walser, [20130610], [20131020]
Voronoi-Regionen
1 Einzugsbereiche von Punkten
Einstiegsbeispiel: Angenommen, die schwarzen Punkte der Abbildung 1 seien Standorte von zum Beispiel SchulhŠusern oder Pumpstationen. Wie finden wir die optimalen Einzugsbereiche? Optimal hei§t hier, dass der Weg zu einem Punkt mšglichst kurz sein soll. Also mšglichst kurze Schulwege. Andere Einkleidung: NŠchster Flughafen fŸr eine allfŠllige Landung in einer Notsituation. Oder: Einsatzbereich von StŸtzpunktfeuerwehren.
Die EinzugskapazitŠt der Attraktor-Punkte wird als unlimitiert angenommen.
Die Einzugsbereiche finden wir mit Mittelsenkrechten.
Abb. 1: Voronoi-Regionen
Die Einzugsbereiche werden als Voronoi-Regionen bezeichnet. Die schwarzen Punkte sind die Zentren der Voronoi-Regionen. Innerhalb einer Voronoi-Region ist ihr Zentrum der nŠchste der Punkte.
Das Netz der roten Mittelsenkrechten hei§t Voronoi-Diagramm. Andere Bezeichnungen sind Thiessen-Polygone oder Dirichlet-Zerlegung.
Die Knotenpunkte des Voronoi-Diagramms sind Mittelpunkte von Kreisen, welche durch Zentren von Voronoi-Regionen laufen.
Die duale Figur zum Voronoi-Diagramm wird als Delone-Triangulation bezeichnet (Abb. 2). Die Voronoi-Regionen zweier in der Delone-Triangulation miteinander verbundener Punkte haben eine Grenze gemeinsam, sind also benachbart.
Abb. 2: Delone-Triangulation
Die Abbildung 3 zeigt eine andere Triangulation. Die grŸn eingezeichneten Strecken verbinden jeweils zwei Punkte, deren Voronoi-Regionen nicht benachbart sind. GefŸhlsmŠ§ig: die grŸnen Strecken sind ãzu langÒ. Die Triangulation ist nicht optimal.
Abb.3: Andere Triangulation
2 Einzugsbereiche von Inseln
Vorstellung: In einem Archipel befinden sich mehrere Inseln. Der Voronoi-Bereich einer Insel ist derjenige Bereich (im Meer), von dessen Punkten aus die Strecke zur Insel am kŸrzesten ist. Minimale Schwimmstrecke fŸr SchiffbrŸchige.
Es werden einige nicht realistische FŠlle untersucht. Sie kšnnen mit DGS (GeoGebra) gezeichnet werden.
2.1 Zwei kreisfšrmige Inseln
Anstelle der Mittelsenkrechten ergibt sich eine Hyperbel als Grenzlinie (Abb. 4).
Abb. 4: Zwei Inseln
2.2 Drei Inseln
Drei Hyperbelbšgen.
Abb. 5: Drei Inseln
2.3 Drei Inseln und Festland
Drei Hyperbelbšgen und zwei Parabelbšgen.
Abb. 6: Drei Inseln und Festland
2.4 Die Insel im Ententeich
Die Grenzlinie ist eine Ellipse.
Abb. 7: Insel im Ententeich
2.5 Zwei Inseln
Ellipsenbšgen und ein Hyperbelbogen
Abb. 8: Zwei Inseln im Ententeich
2.6 Runde Insel im quadratischen Ententeich
Parabelbšgen
Abb. 9: Runde Insel im quadratischen Ententeich
2.7 Quadratische Insel
Mittelparallelen und Parabelbšgen
Abb. 10: Quadratische Insel im quadratischen Ententeich