Komplexität des Brute-Force-Delaunay-Triangulationsalgorithmus

In dem Buch "Computational Geometry: Algorithms and Applications" von Mark de Berg et al. Gibt es einen sehr einfachen Brute-Force-Algorithmus zur Berechnung von Delaunay-Triangulationen. Der Algorithmus verwendet den Begriff der illegalen Kanten - Kanten, die möglicherweise nicht in einer gültigen Delaunay-Triangulation vorkommen und durch einige andere Kanten ersetzt werden müssen. Bei jedem Schritt findet der Algorithmus nur diese unzulässigen Kanten und führt die erforderlichen Verschiebungen durch (sogenannte Kantenflips ), bis keine unzulässigen Kanten mehr vorhanden sind.

Algorithmus LegalTriangulation ( )$T$

Eingabe . Einige Triangulation von einer Punktmenge . Ausgabe . Eine rechtliche Triangulation von .$T$$P$
$P$

während eine illegale Kante enthält do Sei und die beiden Dreiecke neben . Entferne von und füge stattdessen . Rückkehr .$T$$p_ip_j$

$\quad$$p_i p_j p_k$$p_i p_j p_l$$p_ip_j$
$\quad$$p_ip_j$$T$$p_kp_l$
$T$

Ich habe gehört, dass dieser Algorithmus im schlimmsten Fall in läuft . Mir ist jedoch nicht klar, ob diese Aussage richtig ist oder nicht. Wenn ja, wie kann man diese Obergrenze beweisen?$O(n^2)$

Eine Delaunay-Triangulation kann als die untere konvexe Hülle des zum Paraboloid angehobenen 2d-Punkt-Sets betrachtet werden. Wenn Sie also Ihre 2d Punktmenge nehmen und jedem Punkt eine z- Koordinate z i = x 2 i + y 2 1 zuweisen , dann die Projektion der unteren konvexen Hülle in die$(x_i,y_i)$$z$$z_i=x_i^2+y_1^2$ -Ebene gibt Ihnen die Delaunay-Triangulation.$xy$

Was bedeutet es in dieser Perspektive, wenn eine Kante illegal ist? Zuallererst können wir für jede Triangulation T die parabolische Karte verwenden, um eine dreidimensionale (triangulierte) Oberfläche zu erhalten, die nach unten zu T projiziert . Natürlich ist diese Oberfläche nicht unbedingt konvex, wenn sie konvex wäre, wäre T die Delaunay-Triangulation. Einfach ausgedrückt ist die Kante ( p i , p j ) ein Hindernis für die Konvexität der Oberfläche, eine konkave Kante. Wenn wir diese Kante umdrehen, ändern wir die Situation auf der angehobenen Fläche nur lokal. Schauen wir uns also die 4 Punkte an$(p_i,p_j)$$T$$T$$T$$(p_i,p_j)$$p_i,p_j,p_k,p_l$ . In 3d bilden sie einen Tetraeder, der bis in das Viereck hineinragt. Da die beiden Dreiecke und p i p j p l die konkave Kante ( p i , p j ) definieren , definieren die Dreiecke p k p l p i und p k p l p j die konvexe Kante $p_ip_jp_k$$p_ip_jp_l$$(p_i,p_j)$$p_kp_lp_i$$p_kp_lp_j$ . Daher entspricht das Umdrehen einer unzulässigen Kante dem Ersetzen einer konkaven Kante durch eine konvexe Kante beim Anheben. Beachten Sie, dass diese Umkehrungen andere konvexe Kanten in konkave Kanten verwandeln können.$(p_l,p_k)$

Anmerkung: Das Bild ist nicht geometrisch korrekt und sollte nur als Skizze betrachtet werden.

Sei die Triangulation nach dem Flip. Die angehobene Oberfläche T ' „enthält“ die Oberfläche von T . Damit meine ich, dass Sie nur Dreiecke von der Oberfläche von T 'sehen (oder Dreiecke, die sich auf beiden Oberflächen befinden) , wenn Sie die beiden Oberflächen von der x y- Ebene aus betrachten . Man könnte auch sagen, dass die Oberfläche von T ' mehr Volumen einschließt. Auch die Kante ( p i , p j ) liegt jetzt "hinter" der angehobenen Oberfläche, die durch T ' induziert wird , wenn von x $T'$$T'$$T$$xy$$T'$$T'$$(p_i,p_j)$$T'$$xy$ Ebene aus beobachtet wird.

Während der Flip-Sequenz erhalten wir eine Folge von Oberflächen mit streng zunehmendem Volumen. Somit liegt die Kante "hinter" all diesen Oberflächen. Daher kann es während des Kippvorgangs niemals wieder angezeigt werden. Da es nur n wähle 2 mögliche Kanten gibt, haben wir höchstens O ( n 2 ) Flips.$(p_i,p_j)$$n$$O(n^2)$