Triangulación de Delaunay
Una triangulación que maximiza el ángulo más pequeño garantizando que ningún punto quede dentro del círculo circunscrito de ningún triángulo.
Boris Delaunay enunció la condición en 1934. De todas las formas de triangular un conjunto de puntos, Delaunay elige la que evita los triángulos largos y delgados ("astillas"): la condición del círculo vacío fuerza triángulos lo mejor formados posible. Es el dual geométrico del diagrama de Voronoi.
En juegos y gráficos se usa para el terreno (modelos TIN a partir de datos de altura), para generar mallas bien formadas y como base de las navmeshes. Los algoritmos habituales son Bowyer–Watson (pruebas de círculo incrementales) y divide y vencerás. A diferencia del recorte de orejas, no solo le importa dividir una superficie en triángulos, sino la calidad de esos triángulos.