Como os problemas de triangulação de Voronoi e Delaunay são duplos entre si?

Sempre me disseram que o diagrama de Voronoi é o dual do problema da triangulação de Delaunay. Em que sentido eles podem ser duplos um do outro? Eu pensei que problemas duplos (isto é, em programação linear) deveriam produzir a mesma resposta. Claramente, os dois problemas não têm a mesma solução. Como podemos considerá-los duplos?

A resposta simples é que eles são duplos, porque para cada triangulação delaunay existe um e apenas um mosaico voronoi correspondente e vice-versa. Isso é verdade para a maioria dos casos, mas há casos em que a correspondência não é um para um. Por exemplo, no caso em que o mosaico de voronoi é uma grade quadrada regular.

Tanto o mosaico de voronoi quanto a triangulação de delaunay não são triviais para calcular para um determinado conjunto de pontos. Mas uma vez que você tenha encontrado um, o outro é fácil de encontrar.

$P$

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

Dada a triangulação de delaunay, basta conectar os triângulos circunvizinhos vizinhos.

$P$$P$

Apenas para ilustrar o que os outros estão dizendo: o azul abaixo é o diagrama de Voronoi, o vermelho a triangulação dupla de Delaunay. Eles são duplos entre si como gráficos de planos geométricos. A partir do diagrama de Voronoi, é trivial derivar a triangulação de Delaunay. A direção inversa não é tão óbvia, mas continua sendo verdade que, a partir da triangulação de Delaunay e de alguns cálculos, é possível calcular o diagrama de Voronoi.
          
Eu calculei esses diagramas para 50 pontos aleatórios no Mathematica usando o pacote ComputationalGeometry . Veja este link para o meu código.

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

Em certo sentido, isso é semelhante à dualidade existente entre as redes triangulares e hexagonais na física estatística. Os pontos médios das células em uma rede triangular equilateral, quando conectados, formam uma rede hexagonal e vice-versa .

No entanto, deve-se ressaltar que nem todas as pavimentações de Voronoi são duplas de triangulações de Delaunay; essa relação provavelmente é válida apenas para pavimentações Voronoi não ponderadas . Para métodos de mosaico ponderado, nos quais algo diferente da distância euclidiana é usado para determinar as arestas, a correspondência se decompõe.

Para elaborar o comentário de Geoff: a triangulação de Delaunay e os diagramas de Voronoi são "objetos" e não "problemas". Portanto, falar de "soluções" é um pouco complicado.

A dualidade está entre tessalações e triangulações: Para passar da triangulação para a tesselação, você forma o conjunto Voronoi dos vértices da triangulação. Para passar do mosaico de Voronoi para a triangulação de Delaunay, conecte os "pontos médios" de duas células se elas se tocarem.

Os gráficos de Voronoi e Delaunay são chamados de dual por suas propriedades de gráfico. Veja Gráfico Duplo na Wikipedia.