Eine Triangulierung einer Punktmenge in der Ebene (oder höherdimensional) derart, dass kein Punkt im Umkreis irgendeines Dreiecks liegt (Eigenschaft des leeren Umkreises); sie neigt dazu, den kleinsten Winkel der Dreiecke zu maximieren und wird vielfach für Meshes und Interpolation verwendet.

Prinzip

Das Delaunay-Kriterium erzwingt lokale leere-Umkreis-Bedingungen, die bei globaler Erfüllung eine Triangulierung mit vorteilhaften Formeigenschaften erzeugen; das Delaunay-Komplex ist dual zum Voronoi-Diagramm derselben Samenpunkte.

Demonstration

Gegeben eine endliche punktmenge in der Ebene, konstruiere das planare Netzwerk, in dem Dreiecke die Eigenschaft haben, dass ihre Umkreise keine weiteren Eingabepunkte enthalten; durch Edge-Flips auf einer beliebigen Triangulation, bis alle gegenüberliegenden Winkel die Delaunay-Ungleichung erfüllen, erhält man die Delaunay-Triangulierung.

Fehlanwendung

Die Verwendung der Delaunay-Triangulierung für schlecht konditionierte Punktmengen ohne Behandlung kokreisiger oder nahezu kokreisiger Punkte (z. B. Vernachlässigung numerischer Genauigkeit) kann zu mehrdeutigen Flächen, invertierten Elementen im Mesh oder Artefakten bei der Interpolation führen.

Konsequenz

Eine korrekte Delaunay-Triangulierung liefert Meshes mit beschränktem Minimalwinkel, guten Seitenverhältnissen und Umkreismittelpunkten, die in wohl definierten Voronoi-Zellen liegen, was Finite-Elemente-Verfahren und nächstnachbar-Anfragen zugutekommt.

Umkehrung

Die duale Struktur, das Voronoi-Diagramm, kehrt die Perspektive um, indem es Regionen den Samenpunkten zuweist statt Dreiecke aus Punkten zu bilden; diese Umkehr betont Nähe-Partitionierung statt simplizialer Konnektivität.

Abgrenzung

Definiert für diskrete Punktmengen in euklidischen Räumen mit Verallgemeinerung zu höheren Dimensionen als Delaunay-Komplex; ausgeschlossen sind gewichtete Varianten (reguläre Triangulierungen), erzwungene Kanten und nicht-euklidische Metriken ohne Anpassung.

Semantische Spannung

Die Delaunay-Triangulierung steht im Wettbewerb mit begrenzten Triangulierungen und Mesh-Optimierungstechniken: Delaunay optimiert Winkelkriterien global unter der leeren-Umkreis-Regel, während begrenzte Methoden Randtreue oder metrik-spezifische Qualität über reine Delaunay-Optimalität stellen.

Synthese

Die Delaunay-Triangulierung ist das simpliziale Komplex, das dual zum Voronoi-Partition ist und die leere-Umkreis-Bedingung erzwingt; sie liefert Triangulierungen mit nachweislich guten lokalen Formeigenschaften, nützlich für Mesh-Erzeugung, Interpolation und geometrische Algorithmen.