5.1 Voronoi-Diagramme

Motivation (Folie 4)

Eingabe	Menge von Telefonzellen, Postämtern, Sensoren, … und eine aktuelle Position
Ziel	die nächstgelegene Telefonzelle / Post / … finden

Solche Nächste-Nachbarn-Probleme löst man mit Voronoi-Diagrammen. Benannt nach Georgi Woronoi (1868–1908).

Definition 1 (Folie 5)

Sei $P=\{p_1,\dots,p_n\}$ eine Menge von $n$ verschiedenen Punkten (Datenpunkte, Sites) und $d$ eine Metrik. Die Zerlegung der Ebene in $n$ Voronoi-Zellen $V(p_i)$ mit

$q\in V(p_i) \iff d(q,p_i) < d(q,p_j)\quad \forall j\ne i$

heißt Voronoi-Diagramm $\operatorname{Vor}(P)$.

Im Folgenden immer die euklidische Metrik $d(p,q)=\sqrt{(p_x-q_x)^2+(p_y-q_y)^2}$.

Begriffe: Die Zellen sind offen. Punkte mit gleichem Abstand zu zwei nächsten Sites bilden die Voronoi-Kanten, Punkte mit gleichem Abstand zu drei oder mehr nächsten Sites die Voronoi-Knoten.

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

Zellen sind Schnitte von Halbebenen (Folie 6)

Die Punkte, die von $p_i$ und $p_j$ gleich weit entfernt sind, bilden die Mittelsenkrechte (Bisektor) $m_{ij}$, eine Gerade. Sie teilt die Ebene in zwei offene Halbebenen. Die auf der Seite von $p_i$ ist

$h(p_i,p_j)=\{q \mid d(q,p_i)<d(q,p_j)\}.$

Ein Punkt liegt genau dann in $V(p_i)$, wenn er näher an $p_i$ ist als an jedem anderen $p_j$:

$V(p_i)=\bigcap_{j\ne i} h(p_i,p_j).$

Folge: Voronoi-Zellen sind konvex (Schnitt konvexer Mengen ist konvex). Sie sind konvexe Polygone, eventuell unbeschränkt.

(Ergänzung) Das ergibt sofort einen einfachen Algorithmus: Jede Zelle als Schnitt von $n-1$ Halbebenen in $O(n\log n)$, insgesamt $O(n^2\log n)$. Die Demo oben rechnet genau so. Fortunes Algorithmus (5.2) schafft das ganze Diagramm in $O(n\log n)$.

Satz 1: Globale Geometrie und Topologie (Folien 7–8)

Satz 1

Sei $P$ eine Menge von $n\ge3$ verschiedenen Punkten in der Ebene.

1. Liegen alle Punkte auf einer Geraden, besteht $\operatorname{Vor}(P)$ aus $n-1$ parallelen Geraden.
2. Sonst ist $\operatorname{Vor}(P)$ ein zusammenhängender Graph, dessen Kanten Strecken oder Halbgeraden sind.

Beweis. Die Zellen sind als Schnitt von Halbebenen konvex.

1. Kollinear: Die Mittelsenkrechten benachbarter Punkte sind parallel und schneiden sich nicht. Ausprobieren in der Demo mit „kollinear“.
2. Seien $p_i,p_j,p_k$ nicht kollinear.
   • (b) Kanten: Jede Kante ist ein Stück einer Mittelsenkrechten, also Strecke, Halbgerade oder ganze Gerade. Eine ganze Gerade $m_{ij}$ ist aber unmöglich: Es gibt einen Punkt $p_k$, der nicht auf der Geraden durch $p_i, p_j$ liegt. Dann schneidet $m_{ik}$ die Gerade $m_{ij}$, und ab diesem Schnittpunkt ist ein Teil von $m_{ij}$ näher an $p_k$ als an $p_i$ und $p_j$, also keine Voronoi-Kante.
   • (a) Zusammenhang: Angenommen, $\operatorname{Vor}(P)$ zerfällt in zwei Komponenten. Dann muss eine Zelle $V(p_i)$ dazwischen liegen und sie trennen. Eine konvexe Zelle, die die Ebene in zwei Teile trennt, ist ein Streifen zwischen zwei parallelen ganzen Geraden. Das widerspricht (b). □

Satz 2: Globale Kombinatorik (Folien 9–10)

Satz 2

Ein ebenes Voronoi-Diagramm von $n\ge3$ Punkten hat höchstens $n_v = 2n-5$ Voronoi-Knoten und $n_e = 3n-6$ Voronoi-Kanten.

Das Diagramm hat also nur linear viele Knoten und Kanten, obwohl es $\binom n2$ Mittelsenkrechte gibt.

Beweis.

• Nicht alle Punkte sind kollinear (sonst nur $n-1$ Kanten, die Aussage stimmt dann trivial).
• Trick: Die Halbgeraden sind keine richtigen Kanten mit zwei Endpunkten. Man fügt einen Hilfsknoten $v_\infty$ „im Unendlichen“ hinzu und verbindet alle Halbgeraden mit ihm. Dann ist das Diagramm ein zusammenhängender, planarer Graph mit $n_v+1$ Knoten, $n_e$ Kanten und $n$ Flächen (die Zellen).
• Eulersche Formel $n_v - n_e + n_f = 2$: $2 = (n_v+1) - n_e + n. \qquad (1)$
• Grad-Abschätzung: Jede Kante hat zwei Endpunkte, und jeder Knoten (auch $v_\infty$) hat mindestens drei Kanten. Summe der Grade $=2n_e$: $3(n_v+1)\le 2n_e. \qquad (2)$
• Kanten: (1) mal 3 und (2) einsetzen: $6 = 3(n_v+1) - 3n_e + 3n \le 2n_e - 3n_e + 3n = -n_e + 3n \iff n_e\le 3n-6.$
• Knoten: (1) mal 2 und $2n_e\ge 3(n_v+1)$ einsetzen: $4 = 2(n_v+1) - 2n_e + 2n \le 2(n_v+1) - 3(n_v+1) + 2n = -n_v - 1 + 2n \iff n_v \le 2n-5.$ □

Für die Prüfung

Diesen Beweis sollte man an der Tafel vorführen können: $v_\infty$ einführen → Euler → Grad $\ge3$ → zwei Zeilen Umformung. Häufige Nachfrage: Warum hat jeder Knoten Grad ≥ 3? Weil an einem Voronoi-Knoten mindestens drei Zellen zusammenstoßen (sonst wäre es nur ein Punkt auf einer Kante).

Satz 3: Leere Kreise (Folien 11–12)

Sei $c_P(q)$ der größte leere Kreis um $q$: der Kreis mit Mittelpunkt $q$, der keinen Punkt von $P$ im Inneren enthält. Er wächst, bis er den nächsten Punkt (oder mehrere gleich nahe) berührt.

Satz 3

1. Ein Punkt $q$ ist genau dann ein Voronoi-Knoten, wenn $c_P(q)$ mindestens drei Punkte von $P$ auf seinem Rand hat.
2. Ein Bisektor $m_{ij}$ enthält genau dann eine Voronoi-Kante, wenn es einen Punkt $r\in m_{ij}$ gibt, dessen $c_P(r)$ nur $p_i$ und $p_j$ auf dem Rand hat.

Beweis.

1. „⇐“: Hat $c_P(q)$ die Punkte $p_i,p_j,p_k$ auf dem Rand und keinen im Inneren, sind diese drei die nächsten Sites von $q$, alle gleich weit entfernt. Also stoßen in $q$ die drei Zellen $V(p_i), V(p_j), V(p_k)$ zusammen, $q$ ist ein Voronoi-Knoten. „⇒“: Ist $q$ ein Voronoi-Knoten, stoßen dort mindestens drei Zellen zusammen, also liegen mindestens drei gleich nahe Punkte auf dem leeren Kreis um $q$.
2. „⇐“: Hat $c_P(q)$ genau $p_i,p_j$ auf dem Rand, liegt $q$ auf der Grenze von $V(p_i)$ und $V(p_j)$, und nach 1. ist $q$ kein Knoten. Also liegt $q$ im Inneren einer Kante. „⇒“: Enthält $m_{ij}$ eine Kante, hat jeder innere Punkt $q$ der Kante genau $p_i$ und $p_j$ als nächste Sites. □

In der Demo: „Delaunay“ und „Umkreise“ einschalten. Jeder blaue Kreis ist leer, sein Mittelpunkt ist ein Voronoi-Knoten. Mit dem Preset „kreis“ liegen vier Punkte auf einem Kreis: Dort ist der Voronoi-Knoten vom Grad 4, und die Delaunay-Triangulierung ist nicht eindeutig.

Weitere Eigenschaften (Ergänzung)

• $V(p_i)$ ist unbeschränkt ⇔ $p_i$ ist eine Ecke der konvexen Hülle (siehe Komplexität in 5.2).
• Der nächste Nachbar von $p_i$ in $P$ ist ein Voronoi-Nachbar (seine Zelle grenzt an $V(p_i)$).
• Der Mittelpunkt des größten leeren Kreises mit Mittelpunkt in der konvexen Hülle liegt auf einem Voronoi-Knoten oder auf dem Schnitt einer Kante mit dem Hüllrand (Standortplanung: „Wo baue ich die neue Filiale, möglichst weit weg von allen anderen?“).