¿Está Voronoi? Que se ponga

Por Clara Grima, el 28 enero, 2012. Categoría(s): Divulgación • Matemáticas
Ilustración:

Mentiría si dijera que me esperaba la buena acogida que mi anterior entrada sobre los diagramas de Voronoi ha recibido. Cosa que por otra parte viene a corroborar lo que he pensado desde 1995, año que en que la descubrí: ¡la Geometría Computacional mola! Oye, que hasta hemos ganado en la IX edición del Carnaval de Matemáticas.

https://twitter.com/#!/xurxomar/statuses/150156192415629313

A eso vamos, pues.

Por si alguno de vosotros no la ha leído y no sabe qué es un diagrama de Voronoi, aparte de recomendar la citada entrada, recordaré que en el caso de un conjunto finito de puntos del plano, el diagrama de Voronoi de los mismos es la división del plano en regiones, tantas como puntos tengamos, de tal forma que a cada uno ellos le asignamos la región formada por aquellos puntos que están más cercanos a él que ningún otro de los originales.

Ya mencionábamos en aquella entrada la utilidad de este tipo de diagramas, por ejemplo, pasa atribuir la propiedad de un caramelo en el patio de los Lunnis.

En el siguiente vídeo podéis ver cómo se va calculando el diagrama de Voronoi de personas que se están moviendo sobre una plataforma.

[youtube]http://www.youtube.com/watch?v=_Ax4pgtHQDg[/youtube]

Precioso, ¿verdad?

Uno no pararía nunca de encontrar aplicaciones de esta estructura, hasta para crear fractales se puede utilizar.

También existe el juego de Voronoi en el que tenéis que conseguir mayor región de influencia para vosotros que vuestro contrincante, colocando inteligentemente vuestros puntos.

Hasta una aplicación para iPad e iPhone en la que,  con tus dedos, dibujas sobre la pantalla, y el diagrama de Voronoi los puntos que describen esa trayectoria de tus dedos produce algo tan bello como esto:

[youtube]http://www.youtube.com/watch?v=ly8tgaswRo8[/youtube]

También en la serie Numb3rs se habla de ellos…

[youtube]http://www.youtube.com/watch?v=bbKqPcTdv9o[/youtube]

Pero si bien ya dedicamos la entrada anterior a cantar las bondades y utilidades de dicho diagrama en distintas áreas, en ésta que estáis leyendo vamos a hablar sobre su construcción. Que se ponga Voronoi y nos explique cómo se calcula el diagrama, ¿no?

Antes de meternos en faena, dejadme que me pare un poco en contaros cómo algunos usuarios de Twitter encontraron  distintas interpretaciones del diagrama, más… poéticas.

https://twitter.com/#!/xurxomar/status/150159217381224450 https://twitter.com/#!/uncletungsten/status/150369548145672192 https://twitter.com/#!/xurxomar/status/150163732243288064 https://twitter.com/#!/twalmar/status/150170462289264641

Eso sí, si eres estudiante de arquitectura. Igual deberías pensártelo antes de seguir leyendo esta entrada, porque hay ya algunos profesores que están un poco mosqueados con el tema… La que avisa…

Pues nada, al lío.  ¿Cómo se construye el diagrama de Voronoi de un conjunto de puntos en el plano?

Vamos a ir poco a poco, para no agobiarnos.

Si tenemos sólo dos puntos, que en un derroche de originalidad podríamos llamar A y B, para calcular las regiones de Voronoi de éstos, que llamaremos, respectivamente, Vor(A) y Vor(B), sólo hay que dibujar una línea.

Esa línea o recta, es lo que conocemos como mediatriz entre A y B, y se calcula sin más que trazar el segmento que une A con , y por el punto medio de dicho segmento, trazar la recta perpendicular al mismo.

Pues, casi sin despeinarnos, ya hemos superado este escollo.

Vamos a ver qué pasa con 3 puntos,  a los que llamaremos A, B y C.  Comenzamos calculando la  región de Voronoi de A, Vor(A), primero delimitando su territorio frente a su vecino B.

Ahora, delimitamos su territorio frente a C

Y tenemos la región de Voronoi de A, en color violeta en la siguiente figura.

Ahora le toca a B, delimitando su territorio frente a A (en amarillo) y a C (en naranja claro)

Coloreamos en verde Vor(B)

Y, ¡tachán!

Antes de seguir, vamos a fijarnos en este dibujo. Porque el vértice en el que se cortan las tres fronteras de Vor(A), Vor(B) y Vor(C) no es un punto cualquiera. no.  Es el centro de la única circunferencia que pasa por A, B y C. Es más, es el círculo que contiene al triángulo definido por esos tres puntos.

Este hecho, el de que el vértice de Voronoi defina un círculo vacío para tres puntos cercanos, es una propiedad muy, muy, muy interesante que se usa para optimizar modelado de terrenos mediante el uso de triangulaciones. Pero, de Delaunay y sus triangulaciones, ya hablaremos otro día, que pierdo el hilo.

¿Y si tenemos 4 puntos?

Muy bien. Efectivamente. Repetimos el proceso de nuevo: para cada uno de los puntos, calculamos los 3 semiplanos que le pertenecen a él y no a ninguno de los otros 3 y calculamos la intersección de esos  3 semiplanos.  Oye, y sale.  La cosa es que el diagrama de Voronoi vamos a querer calcularlo con el ordenador, y no para 4 puntos, sino, posiblemente para miles.

¿Y si tengo 1000 puntos? ¿Tengo que calcular 1000 veces la intersección de 999 semiplanos? Ya, ya, lo  hace la máquina, pero estará haciendo un montón de cálculos innecesarios, porque de los 999 puntos, serán muy pocos los que compartan frontera en su región de Voronoi con él; de esos 999 semiplanos la mayoría no intervendrán en la región de Voronoi del punto procesado en ese momento.  Estamos haciendo demasiados cálculos, y estamos en crisis… Bromas aparte, buscamos diseño de algoritmos rápidos y eficientes, óptimos.

Vamos a ver si podemos recortar algo y hacerlo más eficientemente.

Hay bastantes algoritmos óptimos (no se pueden mejorar los tiempos de ejecución) para el cálculo del diagrama de Voronoi, os voy a contar uno de ellos, que me gusta mucho.

Se basa en el paradigma de Divide y Vencerás, divide et vinces que diría Julio  César, si pudiera el buen hombre. Pues sí, es una técnica utilizada en el ejército, en la política…y que os recomiendo en la vida en general. Si os veis muy agobiados por un problema de la vida en general o de Matemáticas en particular, tratad de resolver una mitad y luego la otra. ¿Qué la mitad no se deja? Pues la dividimos otra vez y vamos por los cuartos. Y si no, por los octavos, y así, hasta que encontremos un problema abordable y lo resolvemos. Después sólo habrá que pegar los resultados.

Y que, ¡ojo!, no lo digo yo sola, que el mismísimo Descartes lo proponía en su Discurso del método:

Dividir cada una de las dificultades que examinare, en tantas partes fuere posible y en cuantas requiriese su mejor solución.

Y hasta Beppo, al amigo de Momo:

Nunca se ha de pensar en toda la calle de una vez…Sólo hay que pensar en el paso siguiente, en la inspiración siguiente, en la siguiente barrida.

Bueno, que me enrollo. Vamos a ver cómo se pegan dos diagramas de Voronoi y si lo entendemos, fin. Porque cuando tengamos un conjunto, yo que sé, de 50 puntos, lo dividimos en trozos de 2 o 3 puntos, que a ésos le calculamos el diagrama de una patada y luego sólo tendremos que pegar los diagramitas obtenidos para tener el diagrama entero. Eso sí, para dividir el conjunto original en conjuntos de 2 o 3 puntos, vamos a usar restas paralelas de separación, por ejemplo verticales.

Supongamos que tenemos un conjunto de 10 puntos y que ya hemos calculado el diagrama de 6 de ellos por una lado (pegando 2 diagramas de 3) y el de los otros 4, por otro (pegando 2 diagramas de 2). Vamos a pintar esos dos subconjuntos diferentes para facilitar la escritura, y como soy de Sevilla, de verde y rojo, los eternos colores rivales de por aquí.

Para pegar estos dos diagramas, el rojo y el verde,  supongamos que son soldados de dos ejércitos muy, muy enemigos. Un observador neutral quiere atravesar la zona de norte a sur, (que ya hay que tener ganas, sí) y desea hacerlo sin herir susceptibilidades. Para ello, debe pasar siempre a la misma distancia de un soldado rojo que de un soldado verde, claro está.

Pues si viene desde el norte, desde mucho antes de la zona en conflicto, es fácil comprobar, que los dos primeros soldados que lo van a controlar, para que no se acerque más al enemigo que a él mismo, serán  2 puntos, uno rojo y uno verde, de las envolventes convexas roja y verdes, respectivamente, de tal forma que la recta que los une deja a los 10 puntos en el mismo semiplano. Vamos, los dos que están señalados en la figura de la arriba.

Pues, vamos, el observador llegará por el norte caminando sobre la ruta azul, que no es más que la mediatriz entre los dos soldados que lo están vigilando, para que nadie se mosquee.

Cuando el observador se encuentra con una frontera roja, como ocurre en la figura inmediatamente superior, el soldado rojo que lo vigilaba, le cede el puesto a un nuevo soldado de los suyos. ¿A cuál?   Pues, evidentemente al dueño de la nueva región roja en la que ha entrado el caminante.  Entonces, este cambiará su trayectoria a la mediatriz entre el soldado verde original y el nuevo soldado rojo.

Lo siguiente que ha encontrado el observador ha sido una frontera verde (figura anterior), por lo tanto, relevo en las filas verdes. Y el paseante caminará sobre una nueva mediatriz, la del punto rojo que traía y el nuevo verde.

De nuevo llegamos a una frontera roja: cambio de soldado rojo y cambio de mediatriz.

¿Llegamos a una frontera verde? Pues cambiamos de vigilante verde y caminamos por la mediatriz entre él y el rojo que nos estaba vigilando.

Y así, caminando por la ruta en azul, el observador sale sano y salvo porque en ningún momento se ha acercado más a un olor que al otro.

Ahora viene lo bueno.

Si eliminamos las líneas verdes que se han quedado a la derecha del camino azul, y las líneas rojas que se han quedado la derecha, ¿qué es lo que nos queda?

¡Sí, sí, sí! ¡El diagrama de Voronoi de los 10 puntos!

Alucinante, ¿no? Siempre  digo a mis estudiantes de Geometría Computacional que si no alucinan con esto es porque no les queda sangre en el cuerpo. Me miran raro.

Pues bien, este método basado en el Divide y Vencerás es óptimo para el cálculo para el cálculo del Diagrama de Voronoi, mucho más que el de calcular la intersección de semiplanos. Pero no es el único. Hay muchos más, pero no podemos contarlos hoy todos.

Uno que me parece especialmente bello también es debido a Fortune y es conocido como la Línea de  Playa. En pocas palabras, lo que hace es un barrido con una recta, vertical por ejemplo, actualizando la mediatriz entre dicha recta y los puntos que se va encontrando. La mediatriz entre un punto y una recta es una parábola, sí. Si tenemos que dividir el plano entre los puntos que están más cerca a una recta y los que están más cerca a un punto exterior a la misma, lo que nos queda es algo así.

Si queréis ver cómo funciona, os dejo este enlace con una aplicación que os lo muestra, sólo tenéis que añadir con el ratón los puntos que queráis, y a disfrutar.

Una última curiosidad.  Mi amigo y colega José Cáceres pidió a un estudiante suyo que calculara el diagrama de Voronoi de las capitales de provincia españolas en la península, lo hicieron.

Click para ampliar

Como podéis ver en el mapa de la derecha, no difieren tanto ¿Significa eso que las capitales de provincia están bien elegidas desde el punto de vista geométrico?

Termino diciendo que ésta ha sido una manera informal de hablar de algoritmos que calculan el diagrama, sin rigor, sólo para divulgación, ¡no para un examen de Geometría Computacional! Si quieres algo más, no dudes en ponerte en contacto conmigo, porque Voronoi… está sin cobertura 😉

———————-
Esta entrada participa en la Edición 2.10 del Carnaval de Matemáticas, cuyo anfitrión es el blog Resistencia Numantina



Por Clara Grima, publicado el 28 enero, 2012
Categoría(s): Divulgación • Matemáticas