El diagrama de Voronoi, la forma
matemática de dividir el mundo
Esta estructura que sirve para diferenciar el espacio en regiones puede
aplicarse al fútbol, al diagnóstico de tumores o para evitar las colisiones de
barcos en la costa. Dicen que es tan fácil que hasta un niño de tres años puede
entenderlo
CLARA GRIMA
24/04/2017
Actualizado 08/05/2017 a las 19:35h.
Seguramente han oído hablar alguna vez de la eterna cuestión de si las matemáticas se inventan
o se descubren; si están ahí esperando ser descubiertas o si son una construcción del
pensamiento humano que después, casualmente, permiten describir con detalle casi cualquier
fenómeno natural. No se asusten, no vamos a entrar a esta hora en una discusión de tanto calado
porque no es, ni mucho menos, el objetivo de este rincón que la Real Sociedad Matemática
Española tiene en este medio. Lo que sí pretendemos en esta ocasión es mostrarles un ejemplo
en el que las matemáticas son descubiertas porque están escondidas en el concepto natural de
proximidad y/o pertenencia: el diagrama de Voronoi .
El diagrama de Voronoi (que debe su nombre al matemático ruso Georgy Voronoi ) es una
estructura tan sencilla e intuitiva que hasta un niño de tres años puede entenderla.
Efectivamente, hace unos anos me toco ir a la clase de mi hijo (de ninos de tres anos) a explicar a
que me dedicaba en mi trabajo y, como era joven y audaz, me vine arriba y decidí explicarles que
era un diagrama de Voronoi a estos chicos curiosos e inquietos.
Pero, antes de contarles la batallita en el cole de mi hijo, ¿qué es el diagrama de Voronoi? Vamos
a definirlo en dos dimensiones, en el plano. Pero se puede estudiar en cualquier dimensión.
El diagrama de Voronoi de un conjunto de puntos en el plano es la división de dicho plano en
regiones, de tal forma, que a cada punto le asigna una región del plano formada por los puntos
que son más cercanos a él que a ninguno de los otros objetos. Dicho de otra manera, lo que hace
dicho diagrama es dividir el plano en tantas regiones como puntos u tengamos de tal forma que
a cada punto le asignemos la región formada por todo lo que está más cerca de él que de ningún
otro.
Piensen por ejemplo en el plano de una ciudad y dibujen sobre él un punto por cada una de las
farmacias que hay en la misma. En el caso más simple, si solo hubiese una farmacia en la ciudad
la región de Voronoi de dicha farmacia sería toda la ciudad, porque todos están más cerca de
dicha farmacia que de ninguna otra, puesto que no hay más. Fácil, ¿verdad?
Si hubiese dos farmacias, A y B, la ciudad quedaría dividida en dos, los que están más cerca de la
farmacia A que de la farmacia B (llamaremos a esta zona Vor(A)) y los que son más cercanos a la
B que la A (a esta la llamamos Vor(B)). Bueno, y los que están a la misma distancia de los 2. En
honor a Euclides y aquello de que el camino más corto entre dos puntos es la línea recta,
mediremos la distancia en la ciudad como la longitud del segmento que une a dos puntos. Así, los
puntos que están a la misma distancia de ambas farmacias son los que están sobre una recta: la
mediatriz entre los dos puntos que definen las farmacias en el plano y que no es más que la recta
perpendicular al segmento que une A y B por el punto medio de este. Lo hemos dibujado en la
siguiente figura.
En el caso de 3 farmacias, A, B y C, razonando de forma similar y teniendo en cuenta que las
mediatrices son la frontera que delimitan las regiones de influencia 2 a 2 como acabamos de ver,
nos quedaría una division de la ciudad en tres regiones como las que se muestran en la figura
siguiente; cada una de ellas representa la region de Voronoi de cada farmacia, es decir, la zona de
la ciudad que le ‘corresponde’ por ser la farmacia mas cercana.
En general, si tenemos por ejemplo 8 farmacias (8 puntos en el plano) el diagrama de Voronoi
que asigna a cada uno de ellos la region de puntos mas cercanos a el que a ningun otro tendría
un aspecto como el de la figura siguiente:
Y sí, esta construccion la hemos hecho echando de mano de la geometría para calcular las
mediatrices que separan regiones de Voronoi y podría parecer, en principio, ‘sacado’ de la mente
humana porque sí, pero el hecho es que se puede encontrar en infinidad de ejemplos naturales o
se pueden provocar con experimentos caseros muy sencillos.
Si pensamos en los jugadores sobre el terreno de juego como puntos sobre un plano, podemos
asignarle a cada uno de ellos su region de Voronoi que estara formada por los puntos del terreno
de juego que estan mas cerca de cada jugador que del resto. Evidentemente, como los jugadores
no estan quietos, en general, este diagrama ira modificandose con el tiempo, pero nos puede
decir, en cada instante, que equipo esta mejor posicionado en el campo.
Si por ejemplo tenemos dos equipos (equipo rojo y equipo azul) que ocupan esta posición:
La ventaja posicional de un equipo sobre el otro puede que a simple vista no este muy clara, pero
si dibujamos el diagrama de Voronoi de los jugadores y coloreamos con dos colores las regiones
de influencia asociadas a los jugadores de cada uno de los equipos, obtenemos:
Se puede observar que el equipo azul no sólo ocupa mayor región del campo, sino que sus
regiones están todas conectadas, con lo cual se favorecen los pases entre los distintos jugadores
de dicho equipo (cosa que no ocurre con el rojo).
Como hemos dicho, este diagrama irá variando cuando se muevan los jugadores, pero existen
multitud de herramientas que permiten calcular estos diagramas en movimiento. Lo único que
necesitamos es un entrenador que sepa cómo aplicarlo.
En este sentido, en el de regiones de influencia o dominio se pueden encontrar infinidad de
aplicaciones como las del fútbol, las de las farmacias, etc. Pero otro tipo de aplicaciones que igual
no se nos ocurren en primera instancia tiene que ver con las fronteras de las regiones.
Imaginen que en lugar de querer encontrar la farmacia más cercana a ustedes quieren cruzar la
ciudad pasando lo más lejos posible de cualquier farmacia. Igual no lo ven con farmacias, pero
pueden pensar en pastelerías y/o heladerías si están en eso que llaman la operación bikini. En
ese caso, la ruta a seguir nos la dan las líneas de las fronteras del diagrama de Voronoi.
Caminando sobre dichas líneas estaremos siempre lo más alejados posible de las dos pastelerías
que comparten esa línea en su frontera de Voronoi. Esto se utiliza para, por ejemplo, evitar
colisiones de barcos al atravesar zonas escarpadas de la costa.
O, quién sabe, para atacar Pearl Harbor sin que te detecten las restantes bases estadounidenses.
Los puntos de esta imagen representan las bases de EEUU en el Pacífico en 1941. El punto rojo
es Pearl Harbor y los amarillos Aleutianas, Midway y Wake. Las líneas rojas corresponden con el
diagrama de Voronoi de las 4 bases, las líneas blancas senalan la ruta seguida por la flota japonesa
en el ataque
Ah, se me olvidaba. A los niños de 3 años les expliqué la utilidad del diagrama de Voronoi para
identificar quién era el dueño de un caramelo encontrado en la clase (entendiendo que a esas
edades el dueño legítimo es el que está más cerca, claro) y jugamos un rato con una simulación
de caramelos que caían en el patio de juego de los Lunnis.
