Algorithme

Pour rendre une triangulation quelconque ³Delaunay":

• Pour chaque arête non-frontière, trouver les 2 triangles adjacents Tk,Tl de sommets notés q1,q2,q3,q4. Pour l'un des triangles, Tk par exemple, vérifier que le 4eme point n'appartient pas au cercle circonscrit au triangle. Si tel n'est pas le cas, modifier les 2 triangles Tk et Tl en changeant de diagonale dans le quadrilatère q1,q2,q3,q4.
• Refaire cette boucle sur les arêtes jusqu'a ce qu'il n'y ait plus d'échange de diagonale.

Si on choisit de démarrer cet algorithme par l'arête opposée au plus grand angle de la triangulation, alors le procédé est convergent, puisque le plus grand angle décroît strictement à chaque itération.