¿Cómo son los problemas de triangulación de Voronoi Tesselation y Delaunay duales entre sí?

Siempre me han dicho que el diagrama de Voronoi es el doble del problema de triangulación de Delaunay. ¿En qué sentido pueden ser duales el uno del otro? Pensé que se supone que los problemas duales (es decir, en la programación lineal) producen la misma respuesta. Claramente, los dos problemas no tienen la misma solución. ¿Cómo podemos considerarlos duales?

La respuesta simple es que son duales porque para cada triangulación de delaunay existe una y solo una teselación de voronoi correspondiente y viceversa. Eso es cierto para la mayoría de los casos, pero hay casos en los que la correspondencia no es uno a uno. Por ejemplo, en el caso en que la teselación de voronoi es una cuadrícula cuadrada regular.

Tanto la teselación de voronoi como la triangulación de delaunay no son triviales de calcular para un conjunto dado de puntos. Pero una vez que haya encontrado uno, el otro es fácil de encontrar.

En la triangulación de delaunay de un conjunto de puntos, , todos los triángulos son "delaunay", lo que significa que no hay puntos dentro del círculo correspondiente a ninguno de los triángulos.$P$

La teselación de Voronoi de un conjunto de puntos, , consiste en el conjunto de Voronoi células R , tal que para cada punto en R i están más cerca de P i entonces a cualquier otro punto en P .$P$$R$$R_i$$P_i$$P$

Dada la triangulación de Delaunay, simplemente conecte los triángulos vecinos con los centros circunferenciales.

Dado el conjunto de puntos y la teselación de voronoi, simplemente conecte puntos de celdas vecinas. Por supuesto, esto se debe a que conoce el conjunto de puntos P utilizados al construir la teselación de voronoi.$P$$P$

Solo para ilustrar lo que otros dicen: el azul de abajo es el diagrama de Voronoi, el rojo la doble triangulación de Delaunay. Son duales entre sí como gráficos de planos geométricos. Del diagrama de Voronoi es trivial derivar la triangulación de Delaunay. La dirección inversa no es tan obvia, pero sigue siendo cierto que a partir de la triangulación de Delaunay y algunos cálculos puede calcular el diagrama de Voronoi.
          
Calculé estos diagramas para 50 puntos aleatorios en Mathematica usando el paquete ComputationalGeometry . Vea este enlace para mi código.

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

En cierto sentido, esto es similar a la dualidad existente entre redes triangulares y hexagonales en física estadística. Los puntos medios de las celdas en una red triangular equilátera, cuando están conectados, forman una red hexagonal, y viceversa .

Sin embargo, debe señalarse que no todas las teselaciones de Voronoi son duales de triangulaciones de Delaunay; esta relación probablemente sea válida solo para teselaciones de Voronoi no ponderadas . Para los métodos de teselación ponderada, en los que se utiliza algo distinto de la distancia euclidiana para determinar los bordes, la correspondencia se rompe.

Para elaborar el comentario de Geoff: la triangulación de Delaunay y los diagramas de Voronoi son "objetos" en lugar de "problemas". Por lo tanto, hablar de "soluciones" está un poco fuera de lugar.

La dualidad es entre teselaciones y triangulaciones: para pasar de la triangulación a la teselación, se forma el conjunto Voronoi de los vértices de la triangulación. Para pasar de la teselación de Voronoi a la triangulación de Delaunay, conecte los "puntos medios" de dos celdas si se tocan entre sí.

Los gráficos de Voronoi y Delaunay se denominan duales por sus propiedades gráficas. Ver Dual Graph en Wikipedia.