Konstruktion: Das Umkreis-Prinzip

Wenn man zu einem Delaunay-Dreieck den Umkreis bildet, also den eindeutig bestimten Kreis durch die drei Eckpunkte, so kann dieser Umkreis keinen anderen Punkt enthalten. Das hat etwas damit zu tun, daß der Kreismittelpunkt ein Knoten im Voronoi-Diagramm ist.

Durch diese interessante Umkreis-Eigenschaft läßt sich die Delaunay-Triangulation sogar charakterisieren. Genau dann ist eine Triangulation die Delaunay-Triangulation, wenn jeder Dreiecks-Umkreis leer ist.

Diese Eigenschaft nutzen wir jetzt aus, um die Delaunay-Triangulation inkrementell zu konstruieren. Man startet mit einem Dreieck und fügt dann die Punkte nacheinander hinzu. Wenn ein neuer Punkt zu einer bestehenden Delaunay-Triangulation hinzukommt, verbinden wir ihn mit den Eckpunkten des Dreiecks, in dem er liegt.

Dadurch haben wir schon wieder eine Triangulation der Punktmenge erhalten, aber das muß noch nicht die Delaunay-Triangulation sein, denn der neue Punkt könnte ja in den Umkreisen der schon vorhandenen Dreiecke liegen. Wir nehmen also nacheinander die Nachdreiecke her und testen, ob ihr Umkreis den neuen Punkt enthält.

Ist das nicht der Fall, so kann das Dreieck bestehen bleiben. Wenn aber der neue Punkt im Umkreis enthalten ist, so wird ein edge flip ausgeführt. Hierdurch entstehen zwei neue Nachbardreiecke, die auch wieder zu testen sind - und so weiter.

Möglicherweise müssen dabei sehr viele Kanten geflippt werden. Außerdem ist am Anfang auch das Dreieck zu bestimmen, in dem der neue Punkt enthalten ist.

Für jeden der n Punkte wir also schlimmstenfalls linear viel Arbeit verrichtet, so daß dieser einfache Algorithmus maximal quadratische Laufzeit haben kann.

Man kann aber mit feineren Methoden die Delaunay-Triangulation auch in optimaler Zeit n log n konstruieren.