Los diagramas de Voronoi y la triangulación Delaunay

Los diagramas de Voronoi

La mente humana a forjado un dominio espacial durante la evolución de su ser, para nosotros es importante comprender y delimitar áreas espaciales, ya sea para conocimiento de espacios territoriales, búsquedas más cortas de recursos e inclusive para la estética visual. Poco a poco se van mostrando una gran variedad de casos  de alcance limitado, pero conforme el paso del tiempo va llamando la atención de especialistas, da lugar a diversos estudios y aplicaciones hasta llegar a formar una área de investigación.

Los diagramas de Voronoi (ver figura 1) nos ayudan a formar una descomposición ordenada de un espacio determinado y de acuerdo a un conjunto de elementos puntuales (sitios de Voronoi). Este concepto fue utilizado para dar una de las soluciones a la conjetura de Kepler sobre el empaquetamiento óptimo de esferas y Descartes lo emplea en el libro Principios de Filosofía publicado en 1644 para aplicar la teoría de vórtices al funcionamiento del universo, donde las estrellas serían los centros de vórtices celestes y a su vez el sol sería uno de ellos que arrastraría a los planetas a través de un fluido invisible. En el año de 1854 en Londres durante un brote de cólera, John Snow realizó métodos geográficos para identificar el origen de la epidemia y en donde las tomas de agua representaban los sitios de un diagrama de Voronoi. Sin embargo, formalmente los que introducen una definición adecuada a esta estructura espacial son los matemáticos Gustav Dirichlet y Georges Voronoi, quienes las nombran como teselación de Dirichlet [1] en 1850  y diagramas de Voronoi [2] en 1908 respectivamente. Georges Voronoi se da cuenta de la dualidad de esta estructura al conectar dos sitios que tengan una frontera en común, pero es Boris Delone en 1934 quien definió esta propiedad dual como la triangulación Delaunay empleando el método de la esfera vacía [3].

Figura 1. Diagrama de Voronoi

Entre las primeras aplicaciones se remontan a 1911, donde Alfred Thiessen realiza estudios meteorológicos en el cálculo de precipitaciones y en 1927 Paul Niggli reporta investigaciones en cristalografía. Posteriormente hasta la actualidad los diagramas de Voronoi y la triangulación Delanuay se emplean en diversas áreas, por mencionar algunas tenemos: astronomía, cómputo geométrico, construcción de modelos, diseño arquitectónico, geología, meteorología, optimización, robótica y sistemas de información geográfica[4]. 

La estructura geométrica del diagrama está compuesta por arcos y vértices de Voronoi. Algunas propiedades importantes del diagrama de Voronoi en dos dimensiones se listan a continuación:

• Una arista de Voronoi se define como un bisector perpendicular de dos sitios más cercanos pi y pj, ver figura 2 de la izquierda . La condición del círculo que contiene a dos sitios cercanos y la arista que pasa por su centro, debe cumplir que ningún otro sitio debe estar en su interior.
• Un vértice de Voronoi es la intersección de tres aristas del diagrama, también el vértice representa el centro de un círculo definido por tres sitios pi , pj  y pk siempre y cuando el diagrama de Voronoi sea regular o de grado tres, ver figura 2 de la derecha. Como condición del círculo generado por los tres sitios, es que no debe contener otros sitios al interior de él.
• Las regiones que forma el diagrama son polígonos convexos o son regiones sin acotar.

Figura 2.  Condiciones para una arista y un vértice de Voronoi

Triangulación Delaunay

La triangulación Delaunay es un grafo que presenta la característica de ser dual al diagrama de Voronoi, solamente habría que unir los sitios que comparten una arista en común y complementar con una envoltura convexa sea el caso. Pero construir una triangulación Delaunay a partir del diagrama de Voronoi es costoso, por lo que se utilizan otras técnicas para generarlo. En la figura 3 izquierda se muestra una triangulación siguiendo las propiedades del trabajo de Boris Delone y en la figura 3 derecha se muestra la dualidad de ambas estructuras. La triangulación Delaunay es utilizada para la generación de mallas, definiendo un método para conectar un conjunto arbitrario de puntos de manera que forman un conjunto topológicamente válido de triángulos que no se interceptan [5].

     Figura 3. A la izquierda tenemos una Triangulación Delaunay, y en la derecha la dualidad de las ambas estructuras

                                       

Las principales propiedades que tiene la triangulación Delaunay en dos dimensiones son:

• Para un conjuntos de puntos donde  D es una triangulación Delaunay de P si y solo si ningún punto de P se encuentra en el interior de un circulo formado por la circunferencia circunscrita de cualquier triángulo de D, ver figura 4.
•  Se forma una envolvente convexa en los puntos frontera de la triangulación Delaunay.
•  Una triangulación Delaunay es única.

Figura 6. A la izquierda es una triangulación legal y la derecha no lo es.

1.      Dirichlet, G.: Uber die Reduction der positiven quadratischen Formen mit drei  unbestimmten ganzen Zahlen, Journal fur die reine und angewandte Mathematik 40, no. 3, 209-227 (1850)

2.    Voronoi, G.: Nouvelles applications des parametres continus a la theorie des formes quadratiques, Journal fur die reine und angewandte Mathematik 134, no. 4, 198-287 (1908)

3.       Delone , B. N.: Sur la sphere vide, Bulletin of the Academy of Sciences of the U. S. S. R., no. 6, 793-800 (1934)

4.       http://www.voronoi.com

5.       Cofre, R.: http://cybertesis.ubiobio.cl/tesis/2003/cofre_r/html/index-frames.html