5.2 Voronoi-Algorithmus (Fortune)

Überblick (Folie 14)

• Der klassische Algorithmus ist Divide-and-Conquer (Shamos & Hoey 1975) mit $O(n\log n)$, aber schwer zu implementieren (das Zusammenfügen zweier Diagramme ist fummelig).
• Einfacher: der Sweep-Line-Algorithmus von Steven Fortune (1987), ebenfalls $O(n\log n)$.

Grundidee: Eine waagrechte Sweep-Line $\ell$ läuft von oben nach unten und vervollständigt das Diagramm oberhalb.

Das Problem: Anders als beim Segmentschnitt ist das Diagramm direkt über $\ell$ noch nicht fertig. Ein Punkt knapp unter $\ell$ kann eine Zelle beeinflussen, die schon über $\ell$ beginnt. Fertig ist nur der Bereich oberhalb einer stückweise quadratischen Kurve $\beta(x)$, der Strandlinie (beach line).

ℓ = 5.5

fertiges Diagramm blass zeigen einzelne Parabeln

3 Punkt(e) über ℓ erzeugen die Strandlinie aus Parabelbögen. Darüber ist das Diagramm fertig, die Knicke der Strandlinie wandern entlang der Voronoi-Kanten nach unten. 0 Voronoi-Knoten gefunden. Nächstes Ereignis: Punktereignis bei y = 4.

Strandlinie βSweep-Line ℓanstehende Kreisereignissegefundene Voronoi-Knoten

Die Strandlinie (Folien 15–17)

Definition: Die Strandlinie besteht aus allen Punkten, die denselben Abstand zur Sweep-Line $\ell$ und zum nächsten Punkt $p$ oberhalb von $\ell$ haben.

Warum ist darüber alles fertig? Ein Punkt $q$ oberhalb der Strandlinie ist näher an einem Site $p$ über $\ell$ als an $\ell$. Jeder Site unter $\ell$ ist aber weiter von $q$ entfernt als $\ell$. Also kann kein späterer Site $q$ noch „wegschnappen“, die Zuordnung von $q$ ist endgültig.

Die Parabel

Die Punkte $x$-Wert $x$, Höhe $\beta(x)$ mit gleichem Abstand zu $p$ und zu $\ell$:

$\beta(x)-\ell_y = \sqrt{(p_x-x)^2+(p_y-\beta(x))^2}.$

Quadrieren und nach $\beta$ auflösen:

$\beta(x)=\frac{x^2-2p_x x+p_x^2+p_y^2-\ell_y^2}{2(p_y-\ell_y)}.$

Da $p_y>\ell_y$, ist der Nenner positiv: Die Parabeln sind nach oben offen. Ihr Brennpunkt ist $p$, ihre Leitlinie ist $\ell$. Je weiter $\ell$ nach unten wandert, desto breiter werden sie.

Die Strandlinie ist das untere Minimum aller dieser Parabeln (in der Demo: „einzelne Parabeln“ einschalten). Sie besteht aus Parabelbögen (arcs).

Was die Strandlinie verrät (Folie 17)

• Die Übergangspunkte (Knicke) zwischen zwei benachbarten Bögen von $p_i$ und $p_j$ sind gleich weit von $p_i$, $p_j$ und $\ell$ entfernt. Sie liegen also auf der Mittelsenkrechten von $p_i,p_j$ und wandern beim Sweep entlang der Voronoi-Kanten nach unten. So entdeckt man die Kanten.
• Ein neuer Bogen entsteht, wenn $\ell$ einen neuen Punkt erreicht: Punktereignis (site event). Der neue Bogen ist anfangs ein senkrechter Strich (Parabel mit Brennweite 0) und spaltet den Bogen darüber.
• Eine Parabel kann mehrere Bögen zur Strandlinie beitragen (sie wird beim Punktereignis in zwei Teile gespalten).

Lemma 4: Bögen entstehen nur durch Punktereignisse (Folien 18–20)

Lemma 4

Ein Bogen kann nur durch ein Punktereignis auf der Strandlinie erscheinen.

Beweis (Widerspruch). Angenommen, eine schon vorhandene Parabel $\beta_j$ bricht von oben durch die Strandlinie. Das kann auf zwei Arten passieren:

1. Im Inneren eines Bogens $\beta_i$: Dann gäbe es eine Position $\ell_y$, an der sich $\beta_j$ und $\beta_i$ in genau einem Punkt berühren, also mit gleicher Tangente: $\beta_i'(x)=\frac{x-p_{i,x}}{p_{i,y}-\ell_y}=\frac{x-p_{j,x}}{p_{j,y}-\ell_y}=\beta_j'(x).$ Zusammen mit $\beta_i(x)=\beta_j(x)$ folgt $\beta_i\equiv\beta_j$, Widerspruch dazu, dass sie sich nur in einem Punkt berühren.
2. Genau am Übergang zweier Bögen $\beta_i,\beta_k$: Dann gäbe es einen Kreis $C$ durch $p_i, p_j, p_k$, der $\ell$ berührt. Schiebt man $\ell$ weiter nach unten und hält einen Kreis durch $p_j$ tangential an $\ell$, gerät $p_i$ oder $p_k$ in sein Inneres. Also ist $\beta_j$ dort nie der niedrigste Bogen und kann keinen neuen Bogen bilden. □

Folge (Folie 21): Die Strandlinie hat höchstens $2n-1$ Bögen. Jedes Punktereignis fügt einen Bogen hinzu und spaltet einen vorhandenen in zwei, erhöht die Zahl also um höchstens 2. Mit dem ersten Punkt (1 Bogen) ergibt das $1+2(n-1)=2n-1$.

Kreisereignisse (Folien 22–25)

Wann verschwindet ein Bogen? Wenn er zwischen seinen beiden Nachbarn auf einen Punkt zusammenschrumpft. Dann treffen sich zwei Übergangspunkte, also zwei Voronoi-Kanten: ein Voronoi-Knoten entsteht.

Lemma 5

Ein Bogen kann nur bei einem Kreisereignis verschwinden: Ein leerer Kreis $C$ durch die Sites $p_i,p_j,p_k$ dreier (bis dahin) benachbarter Bögen berührt $\ell$ von oben. Kein Punkt von $P$ liegt im Inneren von $C$.

Beweis. Die einzige Alternative wäre, dass die Nachbarbögen $\beta_i$ und $\beta_k$ zur selben Parabel gehören. Dann müssten sie sich wieder vereinen, das hieße aber, dass ein Bogen dieser Parabel neu erscheint, was Lemma 4 verbietet. $\beta_j$ kann nur verschwinden, wenn der Kreis leer ist (sonst hätte der Punkt im Inneren schon vorher einen Bogen dazwischen erzeugt). □

Wo liegt der Voronoi-Knoten? Im Mittelpunkt von $C$, nicht am Berührpunkt mit $\ell$. Das Ereignis wird ausgelöst, wenn $\ell$ den tiefsten Punkt von $C$ erreicht ($y = c_y - r$). Genau dann ist der Mittelpunkt von $p_i,p_j,p_k$ und $\ell$ gleich weit entfernt.

Lemma 6

Alle Voronoi-Knoten werden durch Kreisereignisse erkannt.

Beweis. Zu zeigen ist: Die drei Sites $p_i,p_j,p_k$ eines Voronoi-Knotens haben kurz vor dem Kreisereignis drei benachbarte Bögen erzeugt. Hebt man $\ell$ um ein kleines $\varepsilon>0$ an, gibt es zwei leere Kreise, die $\ell$ berühren und durch $p_i,p_j$ bzw. $p_j,p_k$ gehen. Ihre Mittelpunkte sind Übergangspunkte der Strandlinie. Also waren $\beta_i,\beta_j$ und $\beta_j,\beta_k$ benachbart und haben das Kreisereignis erzeugt. □

In der Demo: Mit „⏩ nächstes Ereignis“ springt $\ell$ von Ereignis zu Ereignis. Gestrichelte orange Kreise sind anstehende Kreisereignisse, rote Punkte gefundene Voronoi-Knoten.

Datenstrukturen (Folien 26–28)

Struktur	Inhalt
Prioritätswarteschlange $Q$	Punkt- und Kreisereignisse, Priorität = $y$-Koordinate (größtes zuerst). Anfangs alle Punktereignisse
Balancierter Suchbaum $T$	die Strandlinie: findet zu jedem Ereignis den betroffenen Bogen in $O(\log n)$
Doppelt verkettete Kantenliste $D$ (DCEL)	das entstehende Voronoi-Diagramm. Gegen Halbgeraden in ein großes Rechteck (Bounding Box) eingebettet

Die Warteschlange $Q$ (Folie 27)

• Punktereignisse sind von Anfang an bekannt.
• Kreisereignisse werden unterwegs berechnet: Für jedes Tripel benachbarter Bögen wird ein Kreisereignis erzeugt, wenn die beiden Übergangspunkte aufeinander zulaufen (die Kanten konvergieren). Laufen sie auseinander, schrumpft der mittlere Bogen nie.
• Ein Punktereignis kann ein vorher erkanntes Kreisereignis ungültig machen (false alarm): Der neue Punkt liegt dann im Kreis, der Kreis ist nicht mehr leer. Dieses Ereignis muss wieder aus $Q$ entfernt werden.

Der Suchbaum $T$ (Folie 28)

• Blätter = Bögen der Strandlinie von links nach rechts. Jedes Blatt speichert
  • einen Zeiger auf den erzeugenden Site,
  • einen Zeiger auf das Kreisereignis, das den Bogen entfernen wird (falls es eins gibt),
  • Zeiger auf die Nachbarbögen.
• Innere Knoten = Übergänge zwischen Bögen, gespeichert als Paar $\langle p_i,p_j\rangle$. Sie speichern
  • Zeiger auf die beiden erzeugenden Sites,
  • einen Zeiger auf die zugehörige Voronoi-Kante in $D$.

Die $x$-Position eines Übergangs hängt von $\ell$ ab. Man speichert sie nicht, sondern berechnet sie beim Suchen aus $p_i$, $p_j$ und $\ell_y$ (Schnitt zweier Parabeln). Wie beim Bentley–Ottmann-Status bleibt die Reihenfolge zwischen Ereignissen gleich.

Algorithmus 1 (Folie 29)

Algorithmus 1: Voronoi-Diagramm(P)
 1: Initialisiere Q mit allen Punktereignissen;
 2: Initialisiere leeren Suchbaum T und leere Kantenliste D;
 3: while (Q ≠ ∅) {
 4:   Nimm das Ereignis mit größtem y aus Q;
 5:   if (Punktereignis) HandleSiteEvent(p_i);
 7:   else HandleCircleEvent(γ);   // γ = Blatt des verschwindenden Bogens
 9: }
10: Die übrigen inneren Knoten von T sind die Halbgeraden:
    Bounding Box um alle Voronoi-Knoten und P berechnen
    und die Halbgeraden dort in D anhängen;

HandleSiteEvent($p_i$) (Folie 30)

1: if (T leer) { p_i in T einfügen; return; }
3: Suche in T das Blatt γ_j des Bogens β_j senkrecht über p_i;
4: if (γ_j zeigt auf ein Kreisereignis) entferne es aus Q;   // false alarm
5: a) Ersetze γ_j durch einen Teilbaum mit drei Blättern:
      Mitte = neuer Site p_i, außen je p_j;
   b) Speichere ⟨p_j, p_i⟩ und ⟨p_i, p_j⟩ in zwei neuen inneren Knoten;
   c) Rebalanciere T;
6: Neue Kante zwischen V(p_i) und V(p_j) in D anlegen;
7: if (β_i und seine zwei rechten Nachbarn erzeugen ein Kreisereignis)
     in Q einfügen und mit den Blättern verlinken;
8: if (β_i und seine zwei linken Nachbarn erzeugen ein Kreisereignis)
     in Q einfügen und mit den Blättern verlinken;

(Genauer: Bei Zeile 7/8 bildet das Tripel aus dem rechten Teilstück von $\beta_j$ und seinen zwei rechten Nachbarn das neue Tripel, denn $\beta_i$ selbst kann nicht verschwinden, er hat ja auf beiden Seiten dieselbe Parabel $\beta_j$ als Nachbarn.)

HandleCircleEvent($\gamma$) (Folie 31)

1: a) Entferne alle Kreisereignisse aus Q, an denen β_j beteiligt ist
      (über die Vorgänger-/Nachfolger-Zeiger in T);
   b) Entferne das Blatt γ des verschwindenden Bogens β_j aus T;
   c) Aktualisiere die inneren Knoten (Übergänge);
   d) Rebalanciere T;
2: Neuen Voronoi-Knoten (Kreismittelpunkt) und neue Kante
   zwischen V(p_i) und V(p_k) in D eintragen
   (p_i, p_k = Sites der Nachbarbögen);
3: if (die neuen Tripel aufeinanderfolgender Bögen um die Lücke
       erzeugen Kreisereignisse) {
4:   in Q einfügen und Zeiger in T setzen;
5: }

Satz 7: Laufzeit (Folie 32)

Satz 7

Algorithmus 1 läuft in $O(n\log n)$ Zeit und braucht $O(n)$ Speicher.

Beweis.

• Jede Operation auf $T$ und $Q$ (Suchen, Einfügen, Löschen) kostet $O(\log n)$, die Initialisierung $O(n)$.
• Jedes Ereignis braucht nur konstant viele solcher Operationen, also $O(\log n)$ pro Ereignis.
• Es gibt $n$ Punktereignisse und höchstens $2n-5$ Kreisereignisse (so viele Voronoi-Knoten gibt es höchstens, Satz 2). Falsche Alarme kosten nichts extra, denn jedes eingefügte Kreisereignis wird höchstens einmal gelöscht und pro Ereignis werden konstant viele eingefügt.
• ⇒ Gesamtlaufzeit $O(n\log n)$.
• Die Strandlinie hat höchstens $2n-1$ Bögen, also brauchen $T$ und $Q$ linearen Speicher, $D$ nach Satz 2 ebenfalls. □

Sonderfälle (Folie 33)

1. Zwei Punkte mit gleichem $y$: Reihenfolge beliebig. Sind es die ersten beiden Punkte, gibt es über dem zweiten noch keinen Bogen (die erste Parabel ist ein senkrechter Strich) → Sonderbehandlung.
2. Zwei Kreisereignisse fallen zusammen: Dann liegen vier Punkte auf einem Kreis. Vereinfachung: nicht gesondert behandeln, sondern eine Kante der Länge 0 erzeugen und im Nachgang entfernen.
3. Punktereignis genau unter einem Übergangspunkt: Einer der Nachbarbögen wird gespalten, sodass ein Bogen der Länge 0 entsteht. Dieser erzeugt sofort ein Kreisereignis, das ihn beim Abarbeiten wieder entfernt.

Komplexität (Folie 34)

• Die Punkte $p_i$ mit unbeschränkter Zelle $V(p_i)$ sind genau die Ecken der konvexen Hülle $\mathcal{CH}(P)$.
• Man findet sie in $O(n)$: Einen hinreichend großen Kreis $C$ um $P$ im Uhrzeigersinn ablaufen und seine Schnitte mit den Voronoi-Kanten bestimmen. Die Zellen, durch die man dabei läuft, sind die unbeschränkten, und zwar in Hüllreihenfolge.
• ⇒ Aus dem Voronoi-Diagramm bekommt man die konvexe Hülle in $O(n)$.
• Die Hülle braucht aber $\Omega(n\log n)$ (2.3 untere Schranke).
• ⇒ Jeder Algorithmus für Voronoi-Diagramme braucht $\Omega(n\log n)$. Fortune ist worst-case-optimal.