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 división de la ciudad en tres regiones como las que se muestran en la figura siguiente; cada una de ellas representa la región de Voronoi de cada farmacia, es decir, la zona de la ciudad que le ‘corresponde’ por ser la farmacia más 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 región de puntos más cercanos a él que a ningún otro tendría un aspecto como el de la figura siguiente:
Y sí, esta construcción 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 ponen caramelos de colores (o chocolatinas en forma de pastillas de colores) en un plato y vierten agua sobre ellos, podrán observar cómo poco a poco se van delimitando las regiones de Voronoi de cada uno de los caramelos (tiñéndose del color correspondiente) hasta que se tocan en la frontera (como se muestra en la foto siguiente) dibujando el diagrama de Voronoi completo. Después, eso sí, se estropea porque se siguen mezclando.
O bien, si se ponen de acuerdo con varios amigos y crean varias pompas de jabón que se van depositando sobre un cristal horizontal, y han tenido cuidado de soplar al mismo ritmo, podrán observar que sobre la superficie en cuestión ‘se dibuja’ una estructura similar a un diagrama de Voronoi en el plano, correspondiente a las regiones influencia de cada pompa de jabón.
Basándose en esta idea Luis M. Escudero y algunos colaboradores han ideado un método que puede servir para revolucionar el diagnóstico automatizado de ciertas formaciones tumorales. Lo que han hecho (en líneas generales), el Dr. Escudero y sus colegas, ha sido es crear un modelo de tejido epitelial (y muscular) ideal mediante el siguiente procedimiento computacional:
(1) se genera un conjunto de puntos al azar;
(2) a dichos puntos se les calcula su diagrama de Voronoi;
(3) se calcula el centro de masas de cada una de las regiones resultantes(esto nos proporciona un nuevo conjunto de puntos);
(4) se calcula el diagrama de Voronoi del nuevo conjunto.
Este proceso se repite hasta tres veces más. El aspecto que tiene este quinto diagrama de Voronoi calculado es el modelo de tejido ideal calculado por el Dr. Escudero (puesto que todas las células son similares, al expandirse, sus fronteras tienden a formar un diagrama de Voronoi). A partir de aquí estos investigadores miden cómo de parecido es el tejido de una muestra real del tejido modelo, si se parecen según ciertos parámetros (geométricos y topológicos), el tejido real está sano; en otro caso se concluye que algunas células no presentan las mismas características físicas que sus vecinas, lo que puede indicar el comienzo de un proceso tumoral. ¿No les parece sorprendente y maravilloso?
El mapa del cólera de John Snow
Convencidos a estas alturas de que el diagrama de Voronoi es una estructura inherente al concepto de proximidad y/o influencia en la naturaleza déjenme que les cuente una de las primeras aplicaciones que del mismo se conocen: el mapa del cólera de John Snow.
A mediados del siglo XIX un brote de cólera azotó la ciudad de Londres; por aquella época no se conocía con exactitud la etiología ni el método de trasmisión de la citada enfermedad, y se debatían entre dos posibilidades: el contagio por contacto con el enfermo, sus ropas y/o pertenencias; y la teoría miasmática que atribuían la trasmisión a condiciones atmosféricas, como los vientos. He aquí que el doctor Snow observó que la distribución de las muertes por cólera seguía un cierto patrón geométrico (o geográfico) muy definido, se concentraban principalmente en una zona de la ciudad. Más aún, las muertes que se producían fuera de esa zona principal eran de personas que habían estado en la misma por alguna razón. John Snow empezó a sospechar que tenía que ver con el agua, más concretamente, con una fuente situada en Broad Street. Para ello, el doctor Snow dibujó sobre el plano de Londres las regiones de influencia de cada una de las fuentes de la ciudad, entendiendo que los habitantes de la misma optarían por buscar agua en la fuente más cercana para ellos (recordemos que no existía el agua corriente). La inmensa mayoría de las muertes se quedaban en la región de influencia de la fuente de Broad Street. Con ello, el doctor Snow descubrió que la causa de la enfermedad fue la contaminación por heces fecales del agua de la citada fuente. Y todo esto antes de que naciera Voronoi.
Desde la época de Snow hasta nuestros días los diagramas de Voronoi han tenido y tienen infinidad de aplicaciones debido, sobre todo, a su estrecha relación con el concepto de regiones de influencia o dominio de los puntos que los generan. Por ejemplo, en el fútbol.
Si pensamos en los jugadores sobre el terreno de juego como puntos sobre un plano, podemos asignarle a cada uno de ellos su región de Voronoi que estará formada por los puntos del terreno de juego que están más cerca de cada jugador que del resto. Evidentemente, como los jugadores no están quietos, en general, este diagrama irá modificándose con el tiempo pero nos puede decir, en cada instante, qué equipo está 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 esté 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 la 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.
