Wie sind die Triangulationsprobleme Voronoi Tesselation und Delaunay dual?

Mir wurde immer gesagt, dass das Voronoi-Diagramm das Duale des Delaunay-Triangulationsproblems ist. Inwiefern können sie Duale voneinander sein? Ich dachte, dass doppelte Probleme (dh in der linearen Programmierung) die gleiche Antwort liefern sollen. Offensichtlich haben die beiden Probleme nicht die gleiche Lösung. Wie können wir sie als Dual betrachten?

Die einfache Antwort ist, dass sie dual sind, weil es für jede Delaunay-Triangulation eine und nur eine entsprechende Voronoi-Tessellation gibt und umgekehrt. Das gilt für die meisten Fälle, aber es gibt Fälle, in denen die Korrespondenz nicht eins zu eins ist. Zum Beispiel in dem Fall, in dem die Voronoi-Tessellation ein reguläres quadratisches Gitter ist.

Sowohl die Voronoi-Tessellation als auch die Delaunay-Triangulation sind für einen bestimmten Satz von Punkten nicht trivial zu berechnen. Aber sobald Sie einen gefunden haben, ist der andere leicht zu finden.

$P$

$P$$R$$R_i$$P_i$$P$

Aufgrund der Delaunay-Triangulation verbinden Sie einfach die benachbarten Dreiecke umkreisen die Zentren.

$P$$P$

Nur um zu veranschaulichen, was andere sagen: Das Blau unten ist das Voronoi-Diagramm, das Rot die doppelte Delaunay-Triangulation. Sie sind als geometrische ebene Graphen dual zueinander. Aus dem Voronoi-Diagramm ist es trivial, die Delaunay-Triangulation abzuleiten. Die umgekehrte Richtung ist nicht so offensichtlich, aber es bleibt wahr, dass Sie aus der Delaunay-Triangulation und einigen Berechnungen das Voronoi-Diagramm berechnen können.
          
Ich habe diese Diagramme für 50 zufällige Punkte in Mathematica mit dem ComputationalGeometry- Paket berechnet . Siehe diesen Link für meinen Code.

${\bf P}$${\bf G}$$G_i$$P_i$$P_j \in {\bf P}, j \neq i$${\bf P}$

In gewissem Sinne ähnelt dies der Dualität zwischen dreieckigen und hexagonalen Gittern in der statistischen Physik. Die Mittelpunkte der Zellen in einem gleichseitigen Dreiecksgitter bilden, wenn sie verbunden sind, ein hexagonales Gitter und umgekehrt .

Es sollte jedoch darauf hingewiesen werden, dass nicht alle Voronoi-Tessellationen Duale von Delaunay-Triangulationen sind; Diese Beziehung gilt wahrscheinlich nur für ungewichtete Voronoi-Tessellationen. Bei gewichteten Tessellierungsmethoden, bei denen zur Bestimmung der Kanten etwas anderes als der euklidische Abstand verwendet wird, bricht die Korrespondenz zusammen.

Um den Kommentar von Geoff näher zu erläutern: Delaunay-Triangulations- und Voronoi-Diagramme sind eher "Objekte" als "Probleme". Von "Lösungen" zu sprechen, ist daher etwas abwegig.

Die Dualität besteht zwischen Tessalierungen und Triangulationen: Um von der Triangulation zur Tesselation zu gelangen, bilden Sie die Voronoi-Menge der Eckpunkte der Triangulation. Um von der Voronoi-Tesselation zur Delaunay-Triangulation zu gelangen, verbinden Sie die "Mittelpunkte" zweier Zellen, wenn sie sich berühren.

Voronoi und Delaunay Graphen werden wegen ihrer Grapheneigenschaften als dual bezeichnet. Siehe Dual Graph auf Wikipedia.