BLOGS

Entradas etiquetadas como ‘Diagramas de Voronoi’

En ocasiones veo Voronois

Hace unos cuanto días, mi santo (espero que Elvira Lindo me perdone por este pequeño plagio que lo ha de considerar como un homenaje), que estaba leyendo el libro de Nate Silver “The signal and the noise” (La señal y el ruido), me señaló una imagen muy curiosa.

Para quien no lo recuerde Nate Silver se hizo bastante famoso después de las últimas elecciones norteamericanas ya que fue capaz de predecir el resultado en todo y cada uno de los estados sin errores (en las anteriores elecciones solo se equivocó en uno de los estados). El método de Silver consiste en acumular tantos datos como sea posible (en el caso de las elecciones: todas las encuestas que estén disponibles así como otros indicios a partir de declaraciones de los candidatos, elementos influyentes, etc.) y entre esos datos tratar de discernir cuáles constituyen la señal (la parte importante a partir de la cual podemos extraer conclusiones) y cuáles son el ruido inherente a toda extracción de datos masiva y que hemos de saber eliminar.

Pues bien, la imagen que me mostraba mi santo era la de la ruta seguida por la flota japonesa para el ataque a la base americana de Pearl Harbor que marcó la entrada de EE. UU. en la Segunda Guerra Mundial e ilustraba que dicha ruta trataba de evitar la detección por parte de los americanos (aunque sostiene Silver que había suficientes señales que fueron obviadas y que hubieran permitido evitar el ataque).

A mi santo aquella imagen le llamó poderosamente la atención y sabía que a mi también me la iba a llamar ¿Por qué? Voy a tratar de explicarlo a continuación.

Una de las páginas con información más exhaustiva sobre la Guerra del Pacífico es The Campaigns of the Pacific War, allí podemos encontrar la ruta que siguió el grueso de la flota japonesa.

ruta

 

Más de uno dirá que la ruta es un tanto extraña, que lo lógico hubiera sido ir en línea recta y, aún más, no haber salido de una base remota de una pequeña isla en el punto más al norte de Japón. Sin embargo, todo tiene su sentido, pero antes permitidme hablar de un viejo “amigo”: Voronoi.

Giorgy Voronoi (1868–1908) fue un matemático que estudió lo que se llama en la actualidad los diagramas de Voronoi. He hablado alguna vez sobre dichas estructuras que aparecen casi en cualquier parte (por ejemplo, aquí y aquí, hasta gané un premio por esta última entrada). Pero digamos, hablando pronto y mal, que dada una colección de puntos en el plano (o en la superficie de la esfera como en el caso que nos ocupa), el diagrama de Voronoi asigna a cada uno de esos puntos su región de influencia. Por ejemplo, en la siguiente figura mostramos 8 puntos y sus regiones de Voronoi. Si los puntos azules representan, por ejemplo, pizzerias, la región de cada punto nos indica cuáles son los puntos más cercanos a esa pizzería que a ninguna otra y, por lo tanto, es una posible división de áreas de reparto.

 

voronoi_2

 

No voy a entrar aquí a contar las propiedades del diagrama de Voronoi, ni a decir cómo construirlo (podéis ver las entradas que acabo de enlazar), pero sí diré que es sabido que si queremos construir una ruta que atraviese por la región en la que se encuentre los puntos y hemos de estar lo más alejados de ellos (para no molestarlos, por ejemplo, si suponemos que son unos nidos de aves que queremos observar), dicha ruta ha de utilizar porciones del diagrama de Voronoi. A estas alturas nos podemos preguntar qué tiene todo esto que ver con Pearl Harbor. Pues bien, en el siguiente mapa muestro las bases navales de EE. UU. en el Pacífico en aquella época (en rojo Pearl Harbor, las otras son en las Aleutianas al norte, Midway y Wake que es la más al este):

bases

 

Creo que todo va a empezar a aclararse con la siguiente imagen, en la que muestro el diagrama de Voronoi de dichas bases:

voronoi

 

¿Qué tal si ahora superponemos la ruta seguida por la flota japonesa con dicho diagrama? Lo que podemos imaginar:

voronoi+ruta

 

Efectivamente, la flota japonesa escogió el punto ideal para salir hacia el ataque, en el sentido de ser el más alejado posible a las bases americanas y, desde entonces, siguió una ruta muy precisa que procuraba estar lo más alejado posible de las bases enemigas hasta que sobrepasaron la vertical de la base en las Aleutianas en la que tomaron bruscamente una ruta de acercamiento hacia Pearl Harbor, aunque se dirigieron primero perpendicularmente hacia la línea imaginaria que marca la frontera entre la región de Voronoi de Midway y de Pearl Harbor lo cual supone evitar, en la medida de lo posible a dichas bases.

Así que ya sabéis: si pretendéis atacar una base enemiga, lo ideal es que sigáis la ruta que os marca el diagrama de Voronoi de los puestos de vigilancia de vuestros rivales, aunque, de todos es conocido que es mejor llevarse bien con todos y hacer el amor y no la guerra.