Triangolazione di Delaunay
Una triangolazione che massimizza l'angolo minimo, garantendo che nessun punto cada dentro il cerchio circoscritto di un triangolo.
Boris Delaunay enunciò la condizione nel 1934. Fra tutti i modi di triangolare un insieme di punti, Delaunay sceglie quello che evita i triangoli lunghi e sottili, detti «sliver»: la condizione del cerchio vuoto impone triangoli quanto più regolari possibile. È il duale geometrico del diagramma di Voronoi.
In giochi e grafica serve per il terreno (modelli TIN ricavati da dati di altezza), per generare mesh ben formate e come base dei navmesh. Gli algoritmi più comuni sono Bowyer–Watson (test incrementali del cerchio) e divide et impera. A differenza dell'ear clipping, non si limita a dividere una superficie in triangoli: gli interessa la qualità di quei triangoli.