Kapitel 5 – Voronoi-Diagramme & Delaunay-Triangulierungen
Folien: 📄 05-voronoi.pdf · Praktikumsaufgabe 4 (randomisierte Delaunay-Triangulierung)
Zwei Strukturen, die eigentlich eine sind:
- Das Voronoi-Diagramm zerlegt die Ebene in Zellen: Jede Zelle enthält alle Orte, die einem bestimmten Datenpunkt am nächsten sind. Anwendung: „Wo ist die nächste Post / der nächste Sensor / das nächste Funkmast?“
- Die Delaunay-Triangulierung verbindet die Punkte, deren Zellen sich berühren. Sie ist der duale Graph des Voronoi-Diagramms und die „schönste“ Triangulierung (maximiert den kleinsten Winkel). Anwendung: Gittererzeugung, Interpolation, Oberflächenrekonstruktion.
Der rote Faden des Kapitels ist der leere Kreis: Voronoi-Knoten sind Mittelpunkte leerer Kreise durch drei Punkte, und genau diese drei Punkte bilden ein Delaunay-Dreieck.
Aufbau
| Abschnitt | Inhalt | Laufzeit |
|---|---|---|
| 5.1 Voronoi-Diagramme | Definition, Halbebenen, Struktur, / , leere Kreise | – |
| 5.2 Fortunes Algorithmus | Sweep-Line, Strandlinie, Punkt- und Kreisereignisse | |
| 5.3 Delaunay-Triangulierung | Dualität, Delaunay-Bedingung, Max-Min-Winkel | – |
| 5.4 Delaunay-Algorithmus | randomisiert inkrementell, Korrektheit, Laufzeit | erwartet |