"Construcción del Diagrama de Voronoi Lejano"

Proyecto Fin de Carrera

Autor: Manuel Romero Muñoz
Tutor: Manuel Abellanas Oar

Departamento de Matemática Aplicada
Facultad de Informática
Universidad Politécnica de Madrid

 
Applet: Voronoi Lejano
Introducción y Objetivos
Dada una nube de N puntos en el plano Euclídeo, denominados sitios, se quiere construir el Diagrama de Voronoi Lejano (DVL).
El DVL pertenece a los denominados Diagramas de Voronoi de orden superior o de orden k.  Si k = 1 el Diagrama de Voronoi es el clásico, en el que cada región incluye los puntos del plano que se encuentran más cerca de cada sitio que de los demás, formando así una región por sitio. Si k = 2 se tiene el Diagrama de Voronoi de orden 2, en el que las regiones incluyen los puntos que están más cercanos a un par de sitios que a cualquier otro. Si k = N-1 las regiones indican los puntos más cercanos a los conjuntos que se puedan formar de N-1 sitios, es decir, las regiones indican los puntos que se encuentran más alejados de uno de los sitios que de los restantes. A este diagrama es al que se denomina Diagrama de Voronoi Lejano, o de orden N-1.
Respecto a  propiedades y características del DVL, decir que todas sus regiones son abiertas y convexas. Los únicos puntos de la nube que generan región son los puntos que se encuentran en el cierre convexo. Un círculo que engloba a los puntos de la nube tiene la propiedad de que cuando su frontera contiene a tres o más puntos, su centro indica un vértice del DVL. Si contiene a dos puntos, su centro se encuentra en una arista del diagrama. De esta forma se puede construir el diagrama y al mismo tiempo se observa qué sitios son los que generan cada uno de los componentes (aristas y vértices) del DVL.

El algoritmo utiliza una estructura DCEL para representar la información de las aristas, vértices y caras del DVL. Esto facilita la construcción del mismo obteniendo una complejidad O (nlogn).

El objetivo del proyecto es familiarizarse con este diagrama observando el aspecto que presenta y pudiendo aprender cómo se obtienen cada una de sus regiones, paso a paso, o mediante el círculo mínimo para saber qué sitios de la nube generan las aristas y vértices del diagrama.

Con el círculo mínimo la construcción es manual, sin ningún orden establecido. Con el sistema paso a paso se va construyendo el DVL mediante un algoritmo incremental en el sentido contrario a las manillas del reloj, comenzando en el sitio mínimo que es el punto más bajo de la nube de puntos.

El applet permite volver a introducir nuevos puntos una vez que se ha construido un Diagrama completo. Pulsando los botones correspondientes el programa construirá el nuevo DVL. La zona de introducción de puntos se muestra al inicio del programa mediante un cuadrado azul, fuera de este cuadrado no se permite introducir puntos.

El applet permite pasar de un estado a otro, es decir, se puede estar construyendo el diagrama con el círculo mínimo y querer pasar a visualizar el Diagrama completo o a su construcción paso a paso. O bien se desea ver el cierre convexo en cualquier momento. El applet permite estos cambios.