¿Diagramas de Voronoi?

¿Alguna vez te has preguntado cómo es que GooglePlaces, Waze, Foursquare y otras aplicaciones saben qué lugares están cerca de ti? Es obvio que utilizando el GPS de tu celular pero no es tan fácil como parece... para ello utilizan algo que se llama DIAGRAMAS DE VORONOI. 

Los diagramas de Voronoi son una de las muchas piezas que conforman las estructuras fundamentales dentro de la geometría computacional, gracias a éste tipo de diagramas es posible "almacenar" información acerca de qué tan próximos están los puntos (en este caso los puntos de interés), gracias al descubrimiento de Gueorgui Voronoi es posible dividir una sección del unvierso (en este caso un mapa) en partes iguales de acuerdo a qué tantos puntos estamos tomando como referencia. Para entenderlo mejor veamos lo siguiente:

Antes de comenzar a seccionar nuestro mapa necesitamos conocer los puntos de interés que vamos a utilizar como referencia, ya sea un restaurante, una zapatería o cualquier otro sitio que queramos.  

Luego de esto, necesitamos conocer la distancia más corta entre todos los puntos (recuerda que la distancia más corta entre dos puntos cualesquiera siempre es la línea recta), después de haber obtenido esa línea debemos trazar la bisectriz (o punto medio) a esa distancia, éste proceso debemos hacerlo con toooooodos los puntos que tengamos...

Una vez hecho lo anterior basta con eliminar las líneas de referencia y lo que queda como exceso en nuestras secciones, quedando algo como lo que sigue:

Ya que hemos obtenido nuestro diagrama de Voronoi es muy sencillo conocer qué lugar nos queda más cerca. Suponiendo que nos encontramos en cualquier sección de la zona amarilla, cuando accedamos a nuestra aplicación para buscar X lugar que nos quede cerca, siempre nos enviará al punto blanco (que es a donde queremos ir) que está dentro de esa zona, si estamos dentro de la zona Roja nos enviará al punto blanco de la sección roja... Interesante no?

Quizá si hacemos todo este proceso a mano nos va a resultar más complicado dependiendo qué tantos puntos estemos considerando, sin embargo nuestros dispositivos lo hacen tan rápido que pareciera que ya recorrieron toda la ciudad y saben bien a donde llevarnos!...