Choisir 4 points qN+1,...,qN+4 formant un rectangle et très éloigné du barycentre des points q1...qN.
Appliquer l'algorithme précédent.
Retirer tous les triangles qui ont des qN+1,..,qN+4 comme sommet.
Si les qN+1,..,qN+4 sont assez éloignés alors cet algorithme marche. En effet considérons d'abord les triangles ayant 2 ou 3 sommets du type qN+1,...,qN+4. ils ne peuvent pas avoir de point q1,...,qN en leur intérieur par construction. Donc tout D est extérieur a chacun de ces triangles et on peut les retirer de la liste.
Soit maintenant un triangle ayant 1 sommets qM du type qN+1,...,qN+4, un sommet qL sur la frontière de D et un sommet interne qk à D, s'il en existe. Formons le quadrilatère avec le triangle adjacent à qkqM. Soit qP les 4eme point. Alors qPqL devrait être une arête car elle vérifie le critère de Delaunay mieux que qkqM si qM est loin. Donc il ne peut y avoir de telle configuration.
Alors nécessairement, par la convexité de D un triangle ayant un sommet du type qN+1,...,qN+4 a ses 2 autres sommets sur la frontière de D. Il est donc extérieur à D et peut être retiré de la liste.