El diagrama de Voronoi (I)

Una entrada para el Carnaval de Matemáticas que empieza con una cita de Groucho Marx que cobrará sentido al final del artículo.

"Claro que lo entiendo. Incluso un niño de cuatro años podría entenderlo. ¡Que me traigan un niño de cuatro años!."

El diagrama de Voronoi es una de las estructuras clásicas en Geometría Computacional (disciplina encargada de resolver problemas geométricos mediante métodos algorítmicos). Es una estructura al tiempo sencilla y poderosa, que parte de una idea tan natural que ha sido descubierta varias veces a lo largo de la historia. De ahí los distintos nombres con los que ha sido conocido: diagrama de Voronoi, polígonos de Thiessen, regiones de Wigner-Seitz, etc.

 

Georgy Voronoi (1868-1908). Foto tomada de Wikipedia.

Pero, ¿qué es el diagrama de Voronoi? Vamos a ilustrarlo con un ejemplo sencillo: supongamos que tenemos una empresa cuya función es ayudar a nuestros clientes a encontrar los servicios más cercanos a su situación actual. Recibimos unas coordenanas por teléfono, web, aplicación móvil... y, en el menor tiempo posible, tenemos que suministrarle la dirección del restaurante, gasolinera, parking, etc. más cercano. ¿Cómo lo hacemos?

Pensemos en el problema de manera geométrica. Partimos de un conjunto de puntos en el plano correspondientes a una categoría de servicios (por ejemplo, gasolineras). Cada consulta de nuestro cliente podemos interpretarla como un nuevo punto que tenemos que emparejar con el más cercano del conjunto inicial. ¿Cómo lo seleccionamos? Fácil, diremos: mido las distancias a cada una de las gasolineras y me quedo con la más pequeña. 

Respuesta correcta, pero no del todo. Repetimos las condiciones del problema: tenemos que dar la respuesta en el menor tiempo posible. ¿Cuánto tardamos con este procedimiento? Lo que nos lleve medir la distancia a cada una de las gasolineras. No podemos hacerlo en menos tiempo porque, a priori, no podemos dejar de comprobar ninguna de ellas. ¿Significa esto que éste el mejor método entre todos los posibles? 

Pues sí y no. Sí, si sólo vamos a tener unos pocos clientes; pero si esperamos que nuestra empresa sea un éxito (y con lo que nos ha constado montarla pongámonos en el mejor de los casos) y recibir miles de peticiones a cada instante, podemos hacerlo un poco mejor. Y aquí alguien ya habrá dado con la respuesta: en lugar de medir la distancia a cada una de las gasolineras hacemos una partición del plano en regiones, de tal forma que si un punto cae dentro de una determinada región entonces podemos decir cuál es su gasolinera más cercana. 

Justamente eso es el diagrama de Voronoi. Sencillo, ¿no?

O, si queremos una defición más precisa: dado un conjunto S de generadores en el plano, el diagrama de Voronoi de S es la teselación (partición) del plano tal que a cada punto de S le asigna la región formada por los puntos del plano que están más cerca suya que de cualquier otro elemento de S. Y viene a tener más o menos esta pinta:

 

No nos engañemos, construir el diagrama no es más rápido que medir la distancia a cada gasolinera. Nada (que funcione) es más rápido que eso. Pero si bien construir el diagrama es más lento, sólo tenemos que hacerlo una vez, y a partir de ahí determinar en qué región está un punto sí puede hacerse antes. Y ahí está el quid de la cuestión. Gastamos un poco más de tiempo al inicio, pero luego nuestras búsquedas serán mucho más rápidas (que es lo que nos exigen nuestros clientes).

Parece sencillo, ¿verdad? Como diría Groucho Marx, incluso un niño de cuatro años podría entenderlo. Y a las pruebas me remito: hace algún tiempo invitaron a unos compañeros de trabajo a ir a la guardería de su hijo a contar a qué se dedicaban. Podían haberse conformado con decir que eran profesores, pero en lugar de eso quisieron contar que eran investigadores, que su campo era la Geometría Computacional y explicarles algunos problemas de la disciplina. ¿Cómo hacerlo con niños de cuatro años? La solución en el siguiente dibujo.

¿Qué Lunni será el primero en llegar al caramelo? El que esté más cerca pero, ¿cómo podemos saberlo rápido rápido?

 

Voilà, el caramelo es de Lucho.