Voronoi-Diagramm

Ein Voronoi-Diagramm teilt die Ebene unter einer Menge von Punkten auf, den sogenannten Keimpunkten: Zu jedem Keimpunkt gehört das Gebiet aller Punkte, die ihm mindestens so nahe sind wie jedem anderen Keimpunkt. Das Bild ist ein Fenster auf die Ebene; die Schattierung innerhalb eines Gebiets dient nur der Darstellung. Die blaue Sonde ist der Mittelpunkt eines leeren Kreises, der bis zum nächsten Keimpunkt reicht. Hier kannst du Keimpunkte verschieben und beobachten, wie sich die Gebiete ihrer Nachbarn ändern, jedes Gebiet von seinem Keimpunkt aus wachsen lassen, die Delaunay-Triangulierung ansehen und die Keimpunkte in Richtung eines Wabenmusters gleichmäßiger verteilen.

Die Punkte, die einem Keimpunkt $p$ mindestens so nahe sind wie einem anderen Keimpunkt $q$, bilden eine Halbebene, begrenzt durch die Mittelsenkrechte von $pq$. Das Gebiet von $p$ ist der Schnitt dieser Halbebenen, einer für jeden anderen Keimpunkt, und daher konvex. Nur einige dieser Mittelsenkrechten werden zu Kanten. Keimpunkte, deren Gebiete eine Kante mit dem Gebiet von $p$ teilen, sind seine Nachbarn; die übrigen Halbebenen enthalten bereits das ganze Gebiet. Der Rahmen begrenzt nur das Fenster. Ein Gebiet reicht genau dann ins Unendliche, wenn sein Keimpunkt auf dem Rand der konvexen Hülle aller Keimpunkte liegt.

Wo drei oder mehr Gebiete zusammentreffen, ist die Ecke von ihren Keimpunkten gleich weit entfernt. Sie ist deshalb der Mittelpunkt eines Kreises durch diese Keimpunkte. Im Inneren dieses Kreises liegt kein Keimpunkt: Ein solcher wäre der Ecke näher, und die Ecke gehörte stattdessen zu seinem Gebiet. Meist treffen genau drei Gebiete an einer Ecke zusammen. Vier treffen zusammen, wenn genau vier Keimpunkte auf einem leeren Kreis liegen, etwa in einem quadratischen Gitter. Bei zufällig verteilten Keimpunkten kommt das fast nie vor.

Wachsen lässt von jedem Keimpunkt eine Kreisscheibe mit derselben Geschwindigkeit wachsen. Jeder Punkt wird zuerst vom nächstgelegenen Keimpunkt erreicht, daher treffen die Fronten genau an den Kanten aufeinander. Die kleine Ansicht zeigt dasselbe Wachstum von der Seite. Über jedem Punkt liegt eine Höhe gleich dem Abstand zum nächsten Keimpunkt: die niedrigste Höhe der Kegel $z = |x - s|$, die auf den Keimpunkten stehen. Die Grate sind die Kanten, und das Wachstum entspricht steigendem Wasser. Der zuletzt überflutete Ort ist der höchste Punkt dieser Landschaft innerhalb des Rahmens, also der Mittelpunkt des größten leeren Kreises, dessen Mittelpunkt im Rahmen liegt.

Triangulierung verbindet zwei Keimpunkte, wenn ihre Gebiete eine Kante teilen, und ergänzt gestrichelte Diagonalen, wenn vier oder mehr Keimpunkte auf einem leeren Kreis liegen, etwa in einem quadratischen Gitter. Sofern nicht alle Keimpunkte auf einer Geraden liegen, entsteht die Delaunay-Triangulierung. Der Umkreis jedes Dreiecks ist der leere Kreis um eine Ecke des Diagramms.

Ausgleichen verschiebt jeden Keimpunkt zum Schwerpunkt seines auf den Rahmen zugeschnittenen Gebiets und berechnet die Gebiete neu, Runde für Runde. Das ist der Lloyd-Algorithmus. Die kleine Grafik zeigt den mittleren quadrierten Abstand eines Punkts im Rahmen zum nächsten Keimpunkt, geteilt durch die Rahmenfläche pro Keimpunkt. Keine Runde kann diesen Wert erhöhen. Bei festen Keimpunkten minimieren die Gebiete der jeweils nächsten Keimpunkte den Wert; bei festen Gebieten tun dies die Schwerpunkte. Die Wabenlinie ist eine untere Schranke: der Wert für gleich große regelmäßige Sechsecke mit den Keimpunkten in ihren Mittelpunkten. Ausgehend von verstreuten Keimpunkten endet der Prozess in einer nahe gelegenen Ruhelage, nicht in einem perfekten Wabenmuster. Meist bleiben Fünf- und Siebenecke nebeneinander bestehen, ähnlich wie Versetzungen in einem Kristall.

Das Diagramm ist nach Georgi Woronoi benannt, der solche Zerlegungen 1908 in beliebigen Dimensionen untersuchte. Die Triangulierung trägt den Namen von Boris Delaunay, der sie 1934 beschrieb.