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

16

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ź pipj
do
Niech pipjpk i pipjpl będą dwoma trójkątami sąsiadującymi z pipj .
Usuń pipj z T i zamiast tego dodaj pkpl .
powrotu T .

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

Michaił Dubow
źródło
5
W powyższym formularzu zajmuje to czas . Jednak przy użyciu stosu można to zrobić w czasie O ( n 2 ) . Możesz spojrzeć na ostatnią stronę w tych notatkach z wykładów . Podstawowym argumentem jest to, że może być co najwyżej ( nO(n3)O(n2) przewraca krawędź. (n2)
rizwanhudda
2
@rizwanhudda: Dlaczego nie udzielić odpowiedzi?
Raphael

Odpowiedzi:

8

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.(xi,yi)zzi=xi2+y12xy

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(pi,pj)TT 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 punktyT(pi,pj)pi,pj,pk,plpipjpk 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łą (pipjpl(pi,pj)pkplpipkplpj . 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.(pl,pk)

Interpretacja 3D Flip 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 jTTTxyTT leży teraz „za” podniesioną powierzchnią indukowaną przez T podczas oglądania zpłaszczyzny x y .(pi,pj)Txy

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.(pi,pj)nO(n2)

A.Schulz
źródło