Delauney Algorithmus

Der Delaunay Algorithmus (Delauney-Triangulation) ist ein gebräuchliches Verfahren, um aus einer Punktemenge ein Dreiecksnetz zu erstellen. Es ist nach dem russischen Mathematiker Boris Nikolajewitsch Delone (1890–1980, franz. Form des Nachnamens: Delaunay) benannt, welcher sich 1934 in einer Veröffentlichung damit auseinandergesetzt hat.

In einer Delaunay-Triangulation erfüllen alle Dreiecke des Dreiecksnetzes die sogenannte Umkreisbedingung: Der Umkreis eines Dreiecks des Netzes darf keine weiteren Punkte der vorgegebenen Punktmenge enthalten. Dadurch weisen die Dreiecke des Netzes möglichst große Innenwinkel auf; mathematisch gesprochen wird „der kleinste Innenwinkel über alle Dreiecke maximiert“. Diese Eigenschaft ist in der Computergrafik sehr erwünscht, denn sie minimiert Rundungsfehler.