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?
