W jaki sposób problemy triselulacji Voronoi Tesselation i Delaunay są dualne?

Zawsze mi mówiono, że diagram Voronoi jest podwójnym problemem triangulacji Delaunaya. W jakim sensie mogą być sobą podwójnymi? Myślałem, że podwójne problemy (tj. W programowaniu liniowym) powinny dać tę samą odpowiedź. Oczywiście dwa problemy nie mają tego samego rozwiązania. Jak możemy uznać je za dualistyczne?

Prosta odpowiedź jest taka, że ​​są one podwójne, ponieważ dla każdej triangulacji delaunay istnieje jedna i tylko jedna odpowiadająca teselacja voronoi i odwrotnie. To prawda w większości przypadków, ale są przypadki, w których korespondencja nie jest jeden do jednego. Na przykład w przypadku, gdy teselacja voronoi jest regularną kwadratową siatką.

Zarówno teselacja voronoi, jak i triangulacja delaunaya nie są trywialne do obliczenia dla danego zestawu punktów. Ale kiedy już znajdziesz taki drugi, łatwo go znaleźć.

$P$

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

Biorąc pod uwagę triangulację delauny, po prostu połącz sąsiednie trójkąty z obwodami.

$P$$P$

Aby zilustrować to, co mówią inni: niebieski poniżej schemat Voronoi, czerwony podwójna triangulacja Delaunaya. Są podwójne względem siebie jako geometryczne wykresy płaskie. Ze schematu Voronoi łatwo jest wyliczyć triangulację Delaunaya. Odwrotny kierunek nie jest tak oczywisty, ale pozostaje prawdą, że z triangulacji Delaunaya i niektórych obliczeń można obliczyć diagram Voronoi.
          
Obliczyłem te diagramy dla 50 losowych punktów w Mathematica przy użyciu pakietu ComputationalGeometry . Zobacz ten link do mojego kodu.

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

W pewnym sensie jest to podobne do dualności istniejącej między siatkami trójkątnymi i heksagonalnymi w fizyce statystycznej. Punkty środkowe komórek w równobocznej sieci trójkątnej, gdy są połączone, tworzą sieć heksagonalną i odwrotnie .

Należy jednak zauważyć, że nie wszystkie teselacje Voronoi są podwójnymi triangulacjami Delaunaya; związek ten prawdopodobnie dotyczy tylko nieważonych teselacji Voronoi. W przypadku metod teselacji ważonej, w których do określenia krawędzi używa się czegoś innego niż odległość euklidesowa, korelacja ulega rozkładowi.

Aby rozwinąć komentarz Geoffa: triangulacja Delaunaya i diagramy Voronoi są raczej „przedmiotami” niż „problemami”. Stąd mówienie o „rozwiązaniach” jest nieco odbiegające od normy.

Dualizm występuje między tessalacjami i triangulacjami: Aby przejść od triangulacji do teselacji, tworzysz zestaw wierzchołków triangulacji Voronoi. Aby przejść od teselacji Voronoi do triangulacji Delaunaya, łączysz „punkty środkowe” dwóch komórek, jeśli się stykają.

Wykresy Voronoi i Delaunay są nazywane podwójnymi ze względu na ich właściwości. Zobacz Dual Graph na Wikipedii.