Eine Unterteilung des Raums in Regionen (Zellen) um eine Menge von Samenpunkten, so dass jede Region aus allen Punkten besteht, die zu ihrem Samen näher sind als zu jedem anderen, und die eine Tesselation für Näheanalyse und nächstnachbar-Anfragen liefert.

Prinzip

Eine Voronoi-Zelle für einen Samen ist die Schnittmenge der Halb-Räume, die durch die Senkrechten der Strecken zwischen diesem Samen und allen anderen Samen bestimmt werden; die Sammlung aller Zellen überdeckt den Bereich mit konvexen Regionen (im euklidischen Fall), deren Benachbartheit die nächstnachbar-Beziehungen kodiert.

Demonstration

Gegeben Samen S = {s1,s2,...,sn} in der Ebene ist die Voronoi-Zelle von si definiert als {x | dist(x,si) ≤ dist(x,sj) für alle j}; durch Konstruktion der senkrechten Punkten zwischen benachbarten Samen entstehen polygonale Zellen deren Ecken Umkreismittelpunkte von Delaunay-Dreiecken sind.

Fehlanwendung

Voronoi-Diagramme mit einer unangemessenen Metrik zu verwenden, ohne die Konstruktion der Trennlinien anzupassen, oder euklidische Eigenschaften (Konvexität, gerade Mediatoren) auf nicht-euklidische Kontexte anzuwenden, kann zu fehlerhaften Zellen und irreführenden Näheangaben führen.

Konsequenz

Voronoi-Diagramme bieten einen kanonischen räumlichen Index für nächstnachbar-Suche, Einflussregionen und räumliches Clustering; ihr Dual, die Delaunay-Triangulierung, unterstützt Mesh-Generierung und effiziente geometrische Abfragen.

Umkehrung

Die Umkehrperspektive liefert die Delaunay-Triangulierung, die Samen zu Simplizes verbindet, deren Umkreismittelpunkte Voronoi-Ecken bilden; diese Umkehr verschiebt den Fokus von Gebietszugehörigkeit zur simplizialen Konnektivität.

Abgrenzung

Definiert für diskrete Samen in metrischen Räumen, in denen Distanzen und Trennlinien wohl definiert sind; in euklidischen Räumen sind Zellen konvexe Polytopen, in gewichteten, anisotropen oder nicht-euklidischen Metriken können Zellen nicht-konvex oder komplizierter strukturiert sein.

Semantische Spannung

Voronoi-Partitionen werden manchmal mit nächstnachbar-Clustern oder dichtebasierten Regionen verwechselt; im Gegensatz zum probabilistischen Clustering sind Voronoi-Zellen deterministische, durch die Metrik induzierte Partitionen und berücksichtigen nicht die Datendichte oder statistisches Glätten ohne Erweiterung.

Synthese

Ein Voronoi-Diagramm ist die durch die Metrik induzierte Partition des Raums in regionszugehörigkeiten zu Samen, erhalten durch Schnittmengen der Halb-Räume aus paarweisen Mediatoren; seine konvexen Zellen und die Dualität zur Delaunay-Triangulierung machen es zu einer fundamentalen Struktur für Nähe, räumliche Indizierung und geometrische Algorithmen.