Triangulación de Voronoi

El dual de los diagramas de Voronoi, o también llamado ``triangulación de Voronoi'' donde una línea es dibujada entre cada punto y todos los puntos cercanos a este. También se le conoce como ``la triangulación de Delaunay'', véase la figura , cabe mencionar que en las figuras y el conjunto de puntos es el mismo y en ellas se pretende mostrar la construcción de un diagrama de Voronoi y la triangulación de Delaunay para los mismos puntos.

El concepto de Voronoi por sí mismo ha inspirado varias técnicas construyendo, aproximaciones más o menos afines al grafo de Voronoi o su dual, la triangulación de Delaunay [Che]. En esta línea se puede mencionar un algoritmo reciente [Nav99a], donde la idea principal en éste y otros algoritmos basados en la triangulación de Delaunay es dividir el espacio para buscar por técnicas espaciales la consulta.

Figura: Formación de la triangulación de Delaunay sobre los puntos de la figura