sábado, 17 de diciembre de 2016

GRAFO DE VORONOI

Esta entrada va dirigida en especial a los alumnos que están participando ahora mismo en la cuarta fase del Programa de Becas Europa y que al leer el pequeño ensayo resumen que he compartido hayan sentido curiosidad por saber que es el grafo de Voronoi y sobre cómo funciona, cómo se usa y para qué se utiliza. A los que no os encontréis en está situación os invito también a leer esta pequeña descripción del grafo Voronoi y a participar en las Becas Europa, como experiencia personal, puedo decir que es un programa que me está resultando bastante interesante y que recomendaría a cualquiera. Sin entretenerme más voy a comenzar con la explicación de este curioso y útil grafo:

En primer lugar, el grafo de Voronoi es aquel que permite hallar las "zonas de influencia" de un punto en el plano. Y ahora, ¿a qué diantres le estoy llamando "zona de influencia"? Una "zona de influencia" de un punto P es aquella región del plano para la cual el punto que se encuentra a una menor distancia de todos los puntos que componen esta región será P. Por ejemplo, si tenemos dos puntos A y B, la "zona de influencia" de estos quedará definida por la mediatriz entre ambos, como vemos en la siguiente figura, donde la zona de A será la azul y la de B la naranja:


Este es un ejemplo muy claro, pero, ¿qué pasaría si tengo más de dos punto?, por ejemplo, 3. En este caso, tendría que dibujar las mediatrices dos a dos y de forma cuidadosa elegir los puntos de corte que delimitarán mis "zonas de influencia". A continuación se muestra en la siguiente imagen, la zona de influencia de A será la azul, la de B la naranja y la de C la amarilla.


El proceso resultaría similar con más puntos, realizamos las mediatrices entre puntos cercanos y tras ello, decidimos de forma intuitiva cuales serán los vértices (puntos de corte de mediatrices) de nuestras "zonas de influencia". Aquí podéis ver un ejemplo con varios puntos y su grafo de Voronoi asociado.


Este grafo se ha utilizado en múltiples ocasiones desde que fuera inventado por el ruso Gueorgui Voronói. En temas tan diversos como estudios sobre la rentabilidad de un posible nuevo establecimiento comercial (se estudiaría cuál sería la "zona de influencia" del local) hasta la planificación de estrategias militares, como cuando los japoneses atacaron a Estados Unidos en la batalla de Pearl Harbor durante la Segunda Guerra Mundial. Ellos afirman que dibujaron un grafo de Voronoi poniendo como puntos las bases estadounidenses del Pacífico, entonces, al hacer volar a sus aviones por las líneas del grafo (los lugares más alejados de los puntos en el grafo) lograron esquivar los detectores del enemigo y presentarse por sorpresa. Ahora, en el proyecto emprendido en Becas Europa, pretendo dibujar el grafo que sea más adecuado para las necesidades de los refugiados y a partir de él, extraer los puntos que cumplen dicho grafo (el proyecto de Becas Europa sobre el que hablo se relaciona en aportar algo que pueda ayudar a la construcción de un nuevo campo de refugiados de 50.000 personas que va a construirse próximamente en Europa y, cómo no, yo he considerado que aquello con lo que más ayuda podía ofrecer era utilizando las matemáticas, la herramienta que mejor domino y con la que más disfruto trabajando). 

Espero que os haya gustado esta pequeña explicación del grafo de Voronoi y que aquellos que estáis participando conmigo en Becas Europa os haya resultado una herramienta interesante y que hayáis entendido mejor que es lo que quiero hacer en mi proyecto y como funciona este grafo.

No hay comentarios:

Publicar un comentario en la entrada