En fin d'algorithme on obtient une triangulation du rectangle qui passe par tous les points donnés. Mais la triangulation n'a pas une ³belle tête".
Une triangulation sera dite de Delaunay si tout cercle circonscrit à un triangle ne contient aucun sommet en son intérieur.
De cette caractérisation géométrique découle la propriété suivante, dont la preuve est immédiate:
Soient q1,q2,q3,q4, 4 points du plan non co-cycliques et formant un quadrilatère convexe ; alors
(i) il existe 2 triangulations de l'enveloppe convexe de ces 4 points : la triangulation de Delaunay et une autre triangulation , qui se déduisent l'une de l'autre en changeant de diagonale dans le quadrilatère q1,q2,q3,q4.
(ii) la triangulation de Delaunay est celle qui maximise la borne inférieure des angles des triangles.