Sección 1: Introducción.

En este tema veremos como los diagrama de Voronoi constituyen una herramienta que, al almacenar toda la información referente a proximidad en una nube de puntos, nos permitirá resolver numerosos problemas en ámbitos muy diversos. En la proxima sección veremos algunos de dichos problemas y en la sección tercera los solucionaremos.

Sección 2: Una colección de problemas de proximidad.

Damos a continuación una serie de problemas que, a pesar de su aparente  disparidad, tienen el denominador común de que la modelización de todos ellos lleva a un problema donde nos preguntamos acerca de relaciones de proximidad entre puntos:

• P1-Tráfico aéreo. De forma simplificada podemos decir que si queremos diseñar una ayuda automática al tráfico aéreo, los dos aviones   que más posibilidades tienen de colisionar son aquellos que se encuentran más cercano.

• P2-Ecología. Es interesante conocer para cada individuo de una especie animal (probablemente en peligro de extinción), cual es el individuo de su misma especie más cercano a él y tratar de encontrar parejas de cercania, el número de parejas de este tipo que se presenten determina un coeficiente que permite medir la posibilidad que tiene una especie de sobrevivir.

• P3-Trazado de redes. Queremos conectar entre sí diversos puntos de tal forma que la longitud total del trazado sea mínima. Este problema tiene aplicaciones en el trazado de redes eléctricas, telefónicas, tuberías, etc.

• P4-Topografía. Dadas las alturas sobre el nivel del mar de diversos puntos sobre los que se han efectuado mediciones precisas, querríamos deducir cual es la altura de un nuevo punto sin necesidad de efectuar nuevas mediciones. 

• P5-Clasificación. En diversas aplicaciones como reconocedores de voz, identificación de particulas elementales, etc., disponemos de diversos patrones fijos y un nuevo elemento (el elemento a clasificar) lo hemos de identificar con uno de dichos patrones. Por ejemplo, en un reconocedor de voz los patrones son las palabras que constituyen nuestro diccionario que han sido previamente grabadas, analizadas y almacenadas, cuando un usario dice algo (una palabra), tratamos de encontrar el patrón de nuestro diccionario que más se aproxima a la palabra que se acaba de pronunciar y la identificamos (reconocemos) con dicho patrón.

A las hora de resolver estos problemas, en primer lugar, es necesario modelizarlos, a ello nos disponemos: en todos los problemas, supondremos que S es una colección de N puntos en el plano:

• El par más cercano. Encontrar la pareja de puntos de S más cercana. Evidentemente esta es una buena modelización del P1 mencionado en la sección anterior, aunque no es difícil encontrar otras aplicaciones de este mismo problema. Obsérvese que hay un número cuadrático de parejas, por lo tanto un algoritmo simple permitiría resolver este problema en tiempo cuadrático.
• Todos los vecinos más cercanos. Para cada punto de S encontrar cuál es su punto más cercano (modelización de P2). Como en el caso anterior, cada punto tiene un número lineal de candidatos a ser su vecino más cercano lo cual llevaría a un algoritmo cuadrático para la resolución de este problema.
• Árbol generador mínimo. Construir un árbol de longitud mínima que tenga a los puntos de S por vértices (si permitieramos añadir nuevos vértices, lo que construiríamos sería un árbol de Steiner, que tiene menor longitud que el árbol generador mínimo pero que es mucho más difícil de construir). Sin embargo ahora el número de árboles es exponencial, por lo tanto, no es claro que exista algoritmo polinomial resolviendo este problema.
• Triangulación. Encontrar una triangulación que tenga a los puntos de S como vértices. Alguien podria decir que en este caso la traducción del P4 no es tan evidente, pero obsérvese que una vez conseguida dicha triangulación, a un punto le podemos suponer con mucha aproximación la altura proporcional de los vértices del triángulo en el que se encuentra (esta es la técnica llamada de interpolación lineal -que tiene muchísimas aplicaciones en campos muy diversos-). En realidad, se puede observar que para que esta técnica sea efectiva, los triángulos han de ser lo más equilatero posible. Al igual que ocurría con los árboles, el número de triangulaciones es exponencial.
• Vecino más cercano. Dado un nuevo punto p, encontrar el elemento de S más cecano a p. En este caso es fácil diseñar un algoritmo lineal que resuelva este problema, veremos que también es posible superar este tiempo.

Sección 3: Resolución de los problemas de proximidad mediante diagramas de Voronoi

Tal y como se ha mencionado anteriormente, todos los problemas mencionados (y muchos más) pueden ser resueltos de forma eficiente utilizando los diagramas de Voronoi, veamos la pueculiaridad de cada caso (S sigue siendo una colección de N puntos en el plano):

Teorema 3.1: Todos los vecinos más cercanos de S puede ser resuelto en tiempo óptimo lineal conociendo Vor(S).

Demostración: Como se ha visto en la Proposición 3.3 del Tema 2, cada vecino de un punto de S define una arista del diagrama de Voronoi, así que sólo debemos buscar entre los vecinos de cada punto y, por la fórmula de Euler, el numero total de vecinos es lineal.                                 

Evidentemente, a partir de todos los vecinos más cercanos, se resuelve el par más cercano en tiempo lineal, tenemos por tanto:

Corolario 3.1: El par más cercano de S puede ser resuelto en tiempo óptimo lineal conociendo Vor(S).

Teorema 3.2: El vecino más cercano   de p puede ser resuelto en tiempo óptimo O(log N) a partir de Vor(S).

Demostración: Basta con encontrar en qué región de Vor(S) se encuentra p y ello como se vió en el Tema 1 puede ser realizado en tiempo O(log N).

Lema 3.1: Dado una partición de S en dos subconjuntos disjuntos S₁ y S₂ la arista más corta que une un vértice de S₁ con uno de S₂ es entre dos vecinos de Vor(S).

Como una consecuencia del Lema 3.1, obtenemos:

Teorema 3.3: El árbol generador mínimo se puede construir en tiempo lineal óptimo a partir de Vor(S).

Por último, nos quedaría por resolver el problema de la triangulación pero a ello le dedicaremos el próximo tema.