Brutalna siła złożoności algorytmu triangulacji Delaunaya

W książce „Geometria obliczeniowa: algorytmy i zastosowania” autorstwa Mark de Berg i wsp. Istnieje bardzo prosty algorytm brutalnej siły do ​​obliczania triangulacji Delaunaya. Algorytm wykorzystuje pojęcie niedozwolonych krawędzi - krawędzi, które mogą nie pojawić się w prawidłowej triangulacji Delaunaya i muszą zostać zastąpione innymi krawędziami. Na każdym kroku algorytm po prostu wykrywa te nielegalne zbocza i wykonuje wymagane przesunięcia (zwane przewracaniem krawędzi ), dopóki nie będzie żadnych nielegalnych zboczy.

Algorytm LegalTriangulation ( $T$ )

Wejście . Niektóre triangulacji $T$ od zadanej $P$ .
Wyjście . Triangulacja prawny $P$ .

podczas gdy $T$ zawiera niedozwoloną krawędź $p_ip_j$
do
$\quad$Niech $p_i p_j p_k$ i $p_i p_j p_l$ będą dwoma trójkątami sąsiadującymi z $p_ip_j$ .
$\quad$Usuń $p_ip_j$ z $T$ i zamiast tego dodaj $p_kp_l$ .
powrotu $T$ .

Słyszałem, że ten algorytm działa w najgorszym przypadku w czasie $O(n^2)$ ; jednak nie jest dla mnie jasne, czy to stwierdzenie jest poprawne, czy nie. Jeśli tak, to jak udowodnić tę górną granicę?

Triangulację Delaunaya można uznać za dolny wypukły kadłub zestawu 2d podniesiony do paraboloidu. Tak więc, jeśli wziąć 2d zadana i przypisać do każdego punktu oo -coordinate oo I = x 2 i + y 2 1 , a następnie występ dolnego kadłuba wypukłej Into the x y -plane daje triangulację Delaunaya.$(x_i,y_i)$$z$$z_i=x_i^2+y_1^2$$xy$

Patrząc z tej perspektywy, co to znaczy, że krawędź jest nielegalna? Przede wszystkim dla każdego triangulacji T możemy użyć paraboliczną mapy, aby dostać 3D (triangulated) powierzchnię, że projekty w dół do T . Oczywiście, powierzchnia ta niekoniecznie musi być wypukła, jeśli byłaby wypukła, p i , p j , p k , p l . W 3d tworzą czworościan, który wystaje do czworokąta. Ponieważ dwa trójkąty p i p j p k i p i $(p_i,p_j)$$T$$T$ byłby triangulacją Delaunaya. Krótko mówiąc, krawędź ( p i , p j ) stanowi przeszkodę dla wypukłości powierzchni,wklęsłąkrawędź. Podczas odwracania tej krawędzi zmieniamy sytuację na podniesionej powierzchni tylko lokalnie. Spójrzmy więc na 4 punkty$T$$(p_i,p_j)$$p_i,p_j,p_k,p_l$$p_ip_jp_k$ określają krawędź wklęsłą ( p i , p j ) , trójkąty p k p l p i i p k p l p j definiują krawędź wypukłą$p_ip_jp_l$$(p_i,p_j)$$p_kp_lp_i$$p_kp_lp_j$ . Dlatego odwrócenie nielegalnej krawędzi odpowiada zastąpieniu krawędzi wklęsłej przez krawędź wypukłą w podnoszeniu. Zauważ, że to odwrócenie może zmienić inne wypukłe krawędzie na wklęsłe krawędzie.$(p_l,p_k)$

Uwaga: Obraz nie jest poprawny geometrycznie i powinien być traktowany jedynie jako szkic.

Niech będzie triangulacją po odwrocie. Podniesiona powierzchnia T " „zawiera”powierzchnię T . Rozumiem przez to, że jeśli oglądasz dwie powierzchnie z płaszczyzny x y , zobaczysz tylko trójkąty z powierzchni T ' (lub trójkąty, które są na obu powierzchniach). Można również powiedzieć, że powierzchnia T ′ obejmuje większą objętość. Również krawędź ( p i , p $T'$$T'$$T$$xy$$T'$$T'$ leży teraz „za” podniesioną powierzchnią indukowaną przez T ′ podczas oglądania zpłaszczyzny x y .$(p_i,p_j)$$T'$$xy$

Podczas sekwencji klap otrzymujemy sekwencję powierzchni o ściśle rosnącej głośności. Zatem krawędź leży „za” wszystkimi tymi powierzchniami. Dlatego nigdy nie może się ponownie pojawić podczas procesu przewracania. Ponieważ istnieje tylko n wybierz 2 możliwe krawędzie, mamy co najwyżej O ( n 2 ) przewroty.$(p_i,p_j)$$n$$O(n^2)$