Delaunay-Triangulierung

• Triangulierung: Eine Triangulierung einer Punktmenge P ist eine simpliziale Zerlegung der konvexen Hülle von P, die ganeu die gegebenen Punkte als Eckpunkte (O-Simplexe) hat.
• In der Ebene: Punktmenge in Dreiecke, im Raum in Tetraeder.
• Delaunay-Triangulierung wichtig, da sie zu einer gleichmäßigen simplizialen Zerlegung der konvexen Hülle führt.
• Delaunay-Umkugelbedingung: Eine Teilmenge $A$ des $\MR ^d$ genügt der D.-Umkugelbedingung bezüglich $n$ gegebener Punkte $p_1,p_2,\dots,p_n \in \MR ^d$ falls $A$ eine umhüllende Hyperkugel besitzt, für die keiner der gegebenen Punkte $p_i$ im Inneren liegt.
• Delaunay-Simplex: Ein D.-Simplex einer Punktmenge ist ein Simplex mit k Eckpunkten aus P ( $1 < k < min[n,d+1]$), der bezüglich P die Umkugelbedingung erfüllt.
• Delaunay-Triangulierung: Eine D.-Triangulierung einer Punktmenge ist eine Triangulierung, die nur aus D.-Simplizia bzgl. der gegebenen Punkte besteht.
• Eigenschaften:
  • Existenzsatz: Zu jeder endlichen Punktmenge existiert eine Delaunay-Triangulierung
  • Eindeutigkeitssatz: Liegen nicht mehr als d+t Punkte auf der hyperkugel, dann ist die Delaunay-Triangulierung eindeutig.
• Die Delaunay-Triangulation stellt eine mächtige Datenstruktur dar, die sowohl für das geometrische Modellieren als auch für die Interpolation von Messwerten oder den Entwurf von netzen für Finite-Elemente-Simulationen von Interesse ist.