Delaunay-Triangulierung

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.