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ę?

— Michaił Dubow
źródło

W powyższym formularzu zajmuje to czas

. Jednak przy użyciu stosu można to zrobić w czasie

. Możesz spojrzeć na ostatnią stronę w tych notatkach z wykładów . Podstawowym argumentem jest to, że może być co najwyżej

O (n^{3})

$O(n^3)$

O (n^{2})

$O(n^2)$

przewraca krawędź.

(\binom{n}{2})

$\binom{n}{2}$

— rizwanhudda

@rizwanhudda: Dlaczego nie udzielić odpowiedzi?

— Raphael

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 -coordinate , a następnie występ dolnego kadłuba wypukłej Into the -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 możemy użyć paraboliczną mapy, aby dostać 3D (triangulated) powierzchnię, że projekty w dół do . Oczywiście, powierzchnia ta niekoniecznie musi być wypukła, jeśli byłaby wypukła, . W 3d tworzą czworościan, który wystaje do czworokąta. Ponieważ dwa trójkąty i $(p_i,p_j)$ $T$ $T$ byłby triangulacją Delaunaya. Krótko mówiąc, krawędź 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łą , trójkąty i 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)$

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

Niech będzie triangulacją po odwrocie. Podniesiona powierzchnia „zawiera”powierzchnię . Rozumiem przez to, że jeśli oglądasz dwie powierzchnie z płaszczyzny , zobaczysz tylko trójkąty z powierzchni (lub trójkąty, które są na obu powierzchniach). Można również powiedzieć, że powierzchnia obejmuje większą objętość. Również krawędź $T'$ $T'$ $T$ $xy$ $T'$ $T'$ leży teraz „za” podniesioną powierzchnią indukowaną przez podczas oglądania zpłaszczyzny . $(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 wybierz 2 możliwe krawędzie, mamy co najwyżej przewroty. $(p_i,p_j)$ $n$ $O(n^2)$

— A.Schulz
źródło