Complexité de l'algorithme de triangulation de Delaunay à force brute

Dans le livre "Computational Geometry: Algorithms and Applications" de Mark de Berg et al., Il existe un algorithme de force brute très simple pour calculer les triangulations de Delaunay. L'algorithme utilise la notion d' arêtes illégales - des arêtes qui peuvent ne pas apparaître dans une triangulation Delaunay valide et qui doivent être remplacées par d'autres arêtes. À chaque étape, l'algorithme trouve simplement ces bords illégaux et effectue les déplacements requis (appelés retournements de bord ) jusqu'à ce qu'il n'y ait pas de bords illégaux.

Algorithme LegalTriangulation ( $T$ )

Entrée . Certains triangulation $T$ d'un ensemble de points $P$ .
Sortie . Une triangulation juridique de $P$ .

tandis que contient un bord illégal p i p j do$T$$p_ip_j$

$\quad$Soit et p i p j p l les deux triangles adjacents à p i p j .$p_i p_j p_k$$p_i p_j p_l$$p_ip_j$
$\quad$Retirez de T et ajoutez p k p l à la place. retour T .$p_ip_j$$T$$p_kp_l$
$T$

J'ai entendu dire que cet algorithme s'exécute en temps dans le pire des cas; cependant, il n'est pas clair pour moi si cette affirmation est correcte ou non. Si oui, comment prouver cette borne supérieure?$O(n^2)$

Une triangulation de Delaunay peut être considérée comme la coque convexe inférieure de l'ensemble de points 2D levée vers le paraboloïde. Ainsi, si vous prenez votre ensemble de points 2D et attribuez à chaque point un z coordonné z i = x 2 i + y 2 1 , alors la projection de la coque convexe inférieure dans l' avion x y vous donne la triangulation de Delaunay.$(x_i,y_i)$$z$$z_i=x_i^2+y_1^2$$xy$

Dans cette perspective, qu'est-ce que cela signifie pour un bord d'être illégal? Tout d' abord, pour chaque triangulation T , nous pouvons utiliser la carte parabolique pour obtenir une surface 3D (triangulé) que les projets jusqu'à T . Bien entendu, cette surface n'est pas nécessairement convexe, si elle était convexe, T serait la triangulation de Delaunay. En termes simples, le bord ( p i , p j ) est une obstruction pour la convexité de la surface, un bord concave . En retournant ce bord, nous changeons la situation sur la surface soulevée uniquement localement. Regardons donc les 4 points$(p_i,p_j)$$T$$T$$T$$(p_i,p_j)$ . En 3d, ils forment un tétraèdre qui se projette vers le quadrilatère. Puisque les deux triangles p i p j p k et p i p j p l définissent le bord concave ( p i , p j ) , les triangles p k p l p i et p k p l p j définissent le bord convexe a$p_i,p_j,p_k,p_l$$p_ip_jp_k$$p_ip_jp_l$$(p_i,p_j)$$p_kp_lp_i$$p_kp_lp_j$ . Par conséquent, le retournement d'un bord illégal correspond au remplacement d'un bord concave par un bord convexe dans le levage. Notez que ces retournements peuvent transformer d'autres bords convexes en bords concaves.$(p_l,p_k)$

Remarque: L'image n'est pas géométriquement correcte et ne doit être considérée que comme une esquisse.

Soit la triangulation après le flip. La surface de levée T ' « contient » la surface de T . J'entends par là que si vous regardez les deux surfaces du plan x y , vous ne voyez que des triangles de la surface de T ' (ou des triangles qui sont dans les deux surfaces). On pourrait également dire que la surface de T ' renferme plus de volume. De plus, le bord ( p i , p j ) se trouve maintenant "derrière" la surface soulevée induite par T ' lors de l'observation depuis le plan x y .$T'$$T'$$T$$xy$$T'$$T'$$(p_i,p_j)$$T'$$xy$

Au cours de la séquence de retournement, nous obtenons une séquence de surfaces avec un volume strictement croissant. Ainsi, le bord se trouve "derrière" toutes ces surfaces. Par conséquent, il ne peut jamais réapparaître pendant le processus de retournement. Puisqu'il n'y a que n choisir 2 arêtes possibles, nous avons au plus O ( n 2 ) flips.$(p_i,p_j)$$n$$O(n^2)$