Eine Methode zur Erstellung eines Dreiecknetzes aus einem Satz von Punkten. Die Dreiecke sind mit der Bedingung definiert, dass innerhalb eines Umkreises um drei Punkte, die ein Dreieck bilden, kein weiterer Punkt liegt (Kriterium des leeren Umkreises). Dies ist eine Methode, die wohlgeformte Dreiecke (nahe an gleichseitigen Dreiecken) produziert. Die resultierenden Dreiecke überlappen sich nicht und vermaschen eine beliebig große Punktmenge flächendeckend und einheitlich. Ein wichtiger rechentechnischer Aspekt ist, dass sich die Delaunay-Triangulation in der Ordnung O (n log(n)) erzeugen lässt. Die Delaunay-Triangulation findet Anwendung bei Digitalen Geländemodellen und bildet dort die TIN-Datenstruktur (Triangular Irregular Network) im Gegensatz zur Grid- bzw. Rasterdatenstruktur. Sie stellt den dualen Graphen zum Voronoi-Diagramm bzw. Thiessen-Diagramm dar, der das Problem der nächsten Nachbarschaft beschreibt.

Quelle siehe: "Geoinformatik-Service"