next up previous contents
Nächste Seite: Einfügen von Punkten Aufwärts: Dynamische Algorithmen Vorherige Seite: Incremental-Algorithmus:   Inhalt


Watson's Algorithmus:

Der hier beschriebene Algorithmus ist auch bekannt unter dem Namen Incremental Delete-and-build-Algorithmus. Vorgestellt wurde der Algorithmus zuerst von [Watson 1981].

Abbildung 3.10: Watson's Algorithmus
\begin{figure} \centerline {\psfig{figure=delaunay/del.eps,width=\textwidth}} \end{figure}

Schritt 1:
Es muss eine grobe Triangulierung erzeugt werden. Dies kann z.B. durch die Triangulierung des umschließenden Polygonzugs geschehen (Abbildung 3.10 a)).
Schritt 2:
Es wird der umgebende Polygonzug des Punktes festgestellt. Dieser Polygonzug ist dadurch gekennzeichnet, dass der neue Punkt innerhalb der Umkreise der Dreiecke liegt. Alle Dreiecke innerhalb des Polygonzuges werden gelöscht (Abbildung 3.10 b)).
Schritt 3:
Innerhalb des Polygonzuges werden neue Dreiecke erzeugt. Jedes neue Dreieck besitzt zwei Punkte auf dem Polygonzug und den neu eingefügten Punkt als Eckpunkte.

Der Watson's Algorithmus ist durch die Suche nach dem Polygonzug vom Laufzeitverhalten her ungünstig. Die Komplexität wird mit ${\cal O}(n^2)$ angegeben.