Delaunay-triangulering
En triangulering som maximerar minsta vinkeln genom att ingen punkt ligger inuti någon triangels omskrivna cirkel.
Boris Delaunay formulerade villkoret 1934. Av alla sätt att triangulera en punktmängd väljer Delaunay det som undviker långa, tunna "sliver"-trianglar — tomma-cirkel-villkoret tvingar fram så välformade trianglar som möjligt. Den är den geometriska dualen till Voronoidiagrammet.
I spel och grafik används den för terräng (TIN-modeller ur höjddata), för att generera jämna meshar och som grund för navmeshar. Vanliga algoritmer är Bowyer–Watson (inkrementell cirkelcheck) och divide-and-conquer. Till skillnad från öronklippning bryr den sig inte bara om att dela upp en yta, utan om kvaliteten på trianglarna.