5.3 Delaunay-Triangulierung

Definition: der duale Graph (Folie 36)

Der duale Graph $\mathcal G$ eines Voronoi-Diagramms heißt Delaunay-Graph. Benannt nach Boris Nikolajewitsch Delone (1890–1980), Mathematiker und Bergsteiger.

Dualität konkret:

Voronoi-Diagramm	Delaunay-Graph
Zelle $V(p_i)$	Knoten $p_i$
Kante zwischen $V(p_i)$ und $V(p_j)$	Kante $\overline{p_ip_j}$
Voronoi-Knoten (Grad 3)	Dreieck
Voronoi-Knoten vom Grad $k$	konvexes $k$-Eck
unbeschränkte Zelle	Punkt auf der konvexen Hülle

Man zeichnet die Delaunay-Kanten als gerade Strecken zwischen den Sites. Sie kreuzen sich nicht (das muss man beweisen, siehe (Ergänzung) unten), die Delaunay-Kante $\overline{p_ip_j}$ muss die zugehörige Voronoi-Kante aber nicht schneiden.

Folgerung

Liegen nie mehr als drei Punkte auf einem Kreis, ist der Delaunay-Graph eine Triangulierung von $P$ und seiner konvexen Hülle, die Delaunay-Triangulierung $\mathcal{DT}(P)$.

Mit Satz 2 hat sie höchstens $3n-6$ Kanten und $2n-5$ Dreiecke, und das sind genau die Schranken aus der Euler-Formel für Triangulierungen. Genauer: Bei $h$ Hüllpunkten hat jede Triangulierung von $P$ genau $2n-2-h$ Dreiecke und $3n-3-h$ Kanten (Ergänzung).

Zellen färben Delaunay Umkreise

n = 8 · Voronoi-Knoten = 9 (≤ 2n−5 = 11) · Voronoi-Kanten = 16 (≤ 3n−6 = 18) · kleinster Winkel 14.0°
Jeder Voronoi-Knoten ist Mittelpunkt eines leeren Kreises durch ≥ 3 Punkte. Mit „Delaunay“ mit der Maus über ein Dreieck fahren zeigt seinen Umkreis. · Klick setzt Punkt, ziehen verschiebt, Rechtsklick löscht.

Voronoi-KantenDelaunay-KantenUmkreise = leere Kreise

Satz 8: Delaunay-Bedingung (Folie 37)

Satz 8

1. Drei Punkte $p_i,p_j,p_k\in P$ gehören genau dann zur selben Fläche des Delaunay-Graphen, wenn ihr Umkreis keinen weiteren Punkt von $P$ (im Inneren) enthält. Das ist die Delaunay-Bedingung.
2. Zwei Punkte $p_i,p_j\in P$ bilden genau dann eine Kante des Delaunay-Graphen, wenn es einen Kreis durch $p_i$ und $p_j$ gibt, der keinen weiteren Punkt von $P$ enthält.

Beweis. Direkt aus Satz 3:

1. Der leere Umkreis von $p_i,p_j,p_k$ ist ein größter leerer Kreis $c_P(q)$ mit drei Punkten auf dem Rand. Nach Satz 3.1 ist sein Mittelpunkt $q$ ein Voronoi-Knoten, und dual dazu ist $p_ip_jp_k$ ein Delaunay-Dreieck. Der Umkreismittelpunkt ist der Voronoi-Knoten dieses Dreiecks.
2. Ein leerer Kreis mit nur $p_i, p_j$ auf dem Rand hat seinen Mittelpunkt auf einer Voronoi-Kante zwischen $V(p_i)$ und $V(p_j)$ (Satz 3.2). Dual dazu ist $\overline{p_ip_j}$ eine Delaunay-Kante. □

Lokale Version (Ergänzung, wichtig für den Algorithmus): Eine Kante $\overline{p_ip_j}$ mit den angrenzenden Dreiecken $p_ip_jp_k$ und $p_ip_jp_l$ heißt legal, wenn $p_l$ nicht im Umkreis von $p_ip_jp_k$ liegt. Satz: Eine Triangulierung ist genau dann Delaunay, wenn alle Kanten legal sind. Lokale Prüfung reicht also.

Der InCircle-Test (Ergänzung)

Für ein gegen den Uhrzeigersinn orientiertes Dreieck $a,b,c$ liegt $d$ genau dann im Umkreis, wenn

$$\det\begin{pmatrix} a_x-d_x & a_y-d_y & (a_x-d_x)^2+(a_y-d_y)^2\\ b_x-d_x & b_y-d_y & (b_x-d_x)^2+(b_y-d_y)^2\\ c_x-d_x & c_y-d_y & (c_x-d_x)^2+(c_y-d_y)^2 \end{pmatrix} > 0.$$

Das ist das Gegenstück zum orient-Test aus Kapitel 1: Hebt man die Punkte auf das Paraboloid $z=x^2+y^2$, wird „im Kreis“ zu „unter der Ebene durch die drei gehobenen Punkte“. Bei $=0$ liegen alle vier auf einem Kreis.

Satz 9: Max-Min-Winkel (Folie 38)

Satz 9

Unter allen Triangulierungen von $P$ maximiert die Delaunay-Triangulierung den kleinsten Innenwinkel aller Dreiecke.

Deshalb ist sie in der Praxis so beliebt: keine dünnen, spitzen Dreiecke, wo es sich vermeiden lässt. Das ist gut für FEM-Netze und Interpolation.

Beweis (auf den Folien „Übung“, hier nach de Berg, Kap. 9):

1. Kantenflip: Zwei Dreiecke $p_ip_jp_k$ und $p_ip_jp_l$ bilden ein Viereck. Ist es konvex, kann man die Diagonale $\overline{p_ip_j}$ durch $\overline{p_kp_l}$ ersetzen.
2. Satz des Thales / Peripheriewinkelsatz: Liegt $p_l$ im Umkreis von $p_ip_jp_k$, ist der Winkel bei $p_l$ über der Sehne größer als der Peripheriewinkel. Daraus folgt: Der Flip auf $\overline{p_kp_l}$ vergrößert den kleinsten der sechs Winkel. Die illegale Kante war also schlechter.
3. Winkelvektor: Sortiert man alle $3t$ Winkel einer Triangulierung aufsteigend, $A(T)=(\alpha_1\le\alpha_2\le\dots)$, wird $A(T)$ durch jeden Flip einer illegalen Kante lexikographisch größer.
4. Es gibt nur endlich viele Triangulierungen. Die mit dem lexikographisch größten Winkelvektor hat also keine illegale Kante mehr und ist nach der lokalen Version von Satz 8 die Delaunay-Triangulierung. Ihr $\alpha_1$ ist maximal. □

In der Demo: Die Statuszeile zeigt den kleinsten Winkel. Verschiebe einen Punkt so, dass ein Dreieck spitz würde. Die Triangulierung „flippt“ lieber eine Kante, als einen kleinen Winkel zu behalten.

Prüfungsfrage

„Warum Delaunay und nicht irgendeine Triangulierung?“ → Max-Min-Winkel (Satz 9), eindeutig bei allgemeiner Lage, dual zu Voronoi (also bekommt man beides auf einmal), effizient berechenbar.

Weitere Eigenschaften (Ergänzung)

• Der nächste Nachbar jedes Punktes ist über eine Delaunay-Kante verbunden. Ebenso sind der euklidische minimale Spannbaum (EMST) und der Gabriel-Graph Teilgraphen von $\mathcal{DT}(P)$.
• Der Rand von $\mathcal{DT}(P)$ ist die konvexe Hülle von $P$.
• Lifting-Abbildung: Die Delaunay-Triangulierung ist die Projektion der unteren konvexen Hülle der auf das Paraboloid $z=x^2+y^2$ gehobenen Punkte. Damit ist Delaunay in 2d „konvexe Hülle in 3d“.
• Nicht kreuzend: Zwei Delaunay-Kanten können sich nicht kreuzen. Sonst hätten beide leere Kreise, und die beiden Kreise müssten jeweils einen Endpunkt der anderen Kante enthalten.