El diagrama de Voronoi (II)

Dentro de las entradas con motivo del Carnaval de Matemáticas os contaba en qué consistía el diagrama de Voronoi. Ahora nos extenderemos un poco con algunas propiedades y algo de historia.

Os recuerdo que, dado un conjunto de puntos S en el plano, su diagrama de Voronoi es la partición del plano en regiones, tal que a cada punto de S le hace corresponder la región formada por aquellos puntos que están más cerca suya que de cualquier otro punto de S.

Sencillo, ¿no? Y al mismo tiempo una herramienta muy potente, ya que almacena gran parte de la información relativa a noción de proximidad entre puntos. Por ejemplo, supongamos que cada generador del diagrama es un detector y queremos atravesar un terreno sin disparar las alarmas, ¿por dónde hemos de ir? Lo más lejos posible de cada detector, claro. Pero con cuidado de que al alejarnos de uno no nos estemos acercando demasiado a otro. ¿Cuáles son los puntos que mantienen una mayor distancia entre detectores? Justamente los que forman las aristas del diagrama.

Otro problema: queremos situar una fábrica contaminante lo más lejos posible de cualquier ciudad, ¿cómo encontrar el sitio idóneo? Recurriendo de nuevo al diagrama de Voronoi, sabiendo que los vértices (puntos que pertenecen al borde de tres regiones) del diagrama son los que están más lejos de los generadores de esas regiones y, por ende, de los demás. Luego nuestra búsqueda se reduce sólo a comprobar los vértices del diagrama.

Además, continuando con el ejemplo de las ciudades, consideremos ahora que queremos unirlas todas mediante fibra óptica, de manera que todas estén conectadas pero con el menor gasto en cable posible. Pues la solución también pasa por estudiar quienes tienen regiones adyacentes en el diagrama de Voronoi.

 

La lista de aplicaciones del diagrama suma y sigue: biología, química, antropología... Una buena página para ver algunas de ellas es The Voronoi Web Site.

Para terminar un poco de historia. La idea detrás del diagrama es tan intuitiva que éste ha aparecido varias veces a lo largo de la historia bajo diversos nombres. Os comento sólo dos de las más antiguas que conocí gracias a una página de la American Mathematical Society. Una primera aparición del diagrama se remonta al S. XVII en un trabajo de Descartes ilustrando cómo se distribuye la materia en el sistema solar.

Otro ejemplo curioso de utilización del diagrama de Voronoi tuvo lugar durante la epidema de cólera de Londres en 1854. Sospechando una relación entre la enfermedad y el suministro de agua, el médico John Snow apuntó sobre un mapa de Londres la dirección de las muertes debidas a la epidemia. Luego dividió la zona en regiones según su cercanía a cada una de las fuentes de agua. Sin saberlo, Snow estaba utilizando un diagrama de Voronoi de las fuentes de Londres y comprobando en qué región había un número mayor de fallecidos. Casi todos caían dentro de una misma región, lo que le permitió relacionar la enfermedad con la contaminación del agua.