Los diagramas de Voronói: Geometría urbana (II)

En nuestro artículo anterior presentamos la Taxi Geometría, que tiene su mejor aplicación al medir distancias en una cuadrícula, y en particular en una ciudad cuyas calles forman una cuadrícula cuadrada o rectangular como es el caso de Manhattan o del Eixample de Barcelona. Hoy vamos a introducir una nueva idea, los diagramas de Voronói, importante para la organización de muchas cosas, en particular en una ciudad con estructura urbana reticular.

Situación

Supongamos que en una ciudad diseñada con las calles formando una cuadrícula cuadrada, hay tres centros asistenciales A, B y C y las instituciones sanitarias precisan dividir la ciudad en tres zonas (una centrada en A, otra en B y otra en C) para que los pacientes de cada zona asistan al centro más próximo y de modo que este centro esté ubicado en su zona.

Para resolver problemas como el mencionado podemos utilizar los llamados diagramas de Voronói y aplicarlos tanto si tomamos la distancia euclídea como la taxidistancia.

Voronói y las áreas geográficas

Gueorgui Feodósievich Voronói (1868-1908), matemático ruso, es conocido por las regiones denominadas “de Voronói” en honor a sus trabajos. En algunos contextos dichas regiones también se conocen como polígonos de Thiesen (meteorólogo contemporáneo de Voronói). Un diagrama de Voronói es una construcción geométrica que permite configurar una partición del plano bajo ciertas condiciones. Por ejemplo, dados n puntos del plano p₁, p₂, p₃,… construir n regiones (cada una de ellas encierra a uno de estos puntos) de manera que todos los puntos de esta región i están más cerca de p_i que del resto de puntos dados inicialmente.

Habitualmente estas regiones se crean uniendo los puntos entre sí y trazando las mediatrices de los segmentos de la unión, que son los puntos frontera por ser equidistantes de dos de los puntos dados. Las intersecciones de estas mediatrices determinan una serie de polígonos alrededor de dichos puntos, de manera que el perímetro de los polígonos generados sea equidistante a los puntos vecinos, designando así su área de influencia.


Los diagramas de Voronói tienen múltiples aplicaciones, debido sobre todo a su estrecha relación con el concepto de regiones de influencia o dominio de los puntos que los generan. La principal aplicación, que no trataremos aquí por no ser objeto del presente artículo, es en la denominada geometría computacional. A nivel más divulgativo, pero no por ello menos relevante, Voronói permite organizar desde la distribución de aeropuertos hasta la distribución de servicios y empresas en regiones y en poblaciones.


La situación más habitual y susceptible de utilizar la Taxi Geometría es el hecho de contar con un conjunto de establecimientos que se desean construir sobre una cierta región geográfica, de tal manera que sus localizaciones sean lo más próximas posible para los elementos interiores a la región. Para ello, se debe hallar una configuración que permita que el número de clientes atraídos sea el más adecuado. Una suposición lógica indica que los clientes o usuarios de los establecimientos irían al más cercano a su domicilio y no a los otros que serán más lejanos. Con base en esta suposición, los diagramas de Voronói otorgan la configuración deseada para el conjunto de establecimientos.

El diagrama de Voronói induce una subdivisión del plano euclidiano (la región geográfica) en función de un conjunto de puntos (los establecimientos), donde a cada punto se le asocia una y solamente una región o subdivisión. Además, cada subdivisión engloba todos los puntos más cercanos al punto asociado que al resto de puntos.

En la imagen se muestran diversos centros de servicios ubicados equitativamente en la ciudad de Barcelona siguiendo los criterios mencionados.


Incluso en el fútbol, si pensamos en los jugadores sobre el terreno de juego como puntos sobre un plano, podemos asignar a cada uno de ellos su región de Voronói 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 indicar, en cada instante, la mejor posición.


Una excelente web para construir regiones de Voronói que proporciona la situación de los puntos al usuario es: http://alexbeutel.com/webgl/voronoi.html. Dicha web construye el diagrama de Voronói con la distancia euclídea usual.

Sin embargo, en una ciudad no podemos construir diagramas de Voronói con la métrica euclídea y nos hará falta considerar la taxidistancia y construir mediatrices con ella. Utilizando Geogebra es posible construir diagramas de Voronói tanto en la métrica euclídea (http://dom.cat/1i12) como en la métrica de Minkowski (https://www.geogebra.org/m/Tke97SmU).

Mediatrices en la taxidistancia

Si tenemos dos puntos sobre el plano, A y B, los puntos que están a la mitad de camino entre A y B, a la misma distancia de ambos, definen una recta que conocemos como mediatriz. Para ello construimos el rectángulo definido por A y B, con longitudes a y b. Se observa que la taxidistancia entre A y B es a + b.


Para construir la mediatriz tenemos que construir el lugar geométrico de los puntos que están a distancia (a+b)/2 de los puntos A y B. Para ello consideramos los puntos P y Q que se encuentran a distancia (a+b)/2 según la imagen.


Es fácil observar que todos los puntos que están en el segmento PQ equidistan de A y B una distancia de (a+b)/2. De la misma forma se observa que si añadimos las semirrectas verticales por P y Q, los puntos de dichas semirrectas también verifican que la distancia a A y B es de (a+b)/2. Con la argumentación realizada se puede afirmar que la mediatriz es la poligonal que divide el plano en dos regiones de Voronói, tal como se aprecia en la siguiente ilustración:


En síntesis, el diagrama de Voronói determinado por A y B es:


Un taxi en el barrio de Voronói: Solución a la situación planteada

Ahora podemos volver a la situación real propuesta al inicio del artículo: supongamos que en una ciudad, diseñada con las calles formando una cuadrícula cuadrada, hay tres centros asistenciales A, B y C, y las instituciones precisan dividir la ciudad en tres zonas para que los pacientes de cada zona asistan al centro más próximo y este centro esté ubicado en su zona. Para ello supondremos que se desplazan según el criterio de la distancia del taxi y resolveremos el problema usando diagramas de Voronói. Si construimos las respectivas mediatrices en Taxi Geometría y se obtiene el diagrama plasmado en la imagen:

Es fácil comprobar que cualquier persona de la zona donde se encuentra el punto A, está más cerca de A que de B o C. Análogamente para los puntos de las otras zonas. Si la imagen anterior se corresponde con la situación de los tres centros sanitarios de la hipotética ciudad se observa que la distancia del taxi entre el centro A y el B es 8, entre A y C es 12 y entre B y C es 10. En la imagen destacan las zonas que son el área de influencia de cada centro, es decir, los pacientes que viven en cada una de esas áreas asistirá al centro asistencial que está en la misma, ya que es el que les queda más cerca.

Además, el diagrama permite analizar otros problemas similares. Si, por ejemplo, un restaurante desea abrir un local, puede pensar hacerlo en un punto equidistante de los tres centros sanitarios. Entonces, de acuerdo con el diagrama, deberá construirlo en la intersección de las tres fronteras.

Un ejemplo complementario

Consideremos ahora un ejemplo relacionado con el circuncentro, que es el centro de la circunferencia que pasa por los tres vértices de un triángulo, y que se corresponde con la intersección de las mediatrices de cada lado del triángulo. Por tanto, el cincuncentro de un triángulo es el punto que equidista de los tres vértices del triángulo.

Supongamos una familia formada por tres miembros en la que el padre trabaja en un punto A situado en (-3,-1), la madre en el punto B = (3,3) y el hijo va a una escuela situada en el punto C = (0,-3).

La pregunta es: ¿dónde tienen que vivir para que cada uno tenga que caminar la misma distancia para desplazarse al trabajo o a la escuela?

En geometría euclídea tendríamos que en este caso el punto sería el (0.25, 0.63) tal como muestra la imagen:


En Taxi Geometría, la recta r representa la mediatriz del segmento AC, s la mediatriz del segmento AB y t la mediatriz de BC. El punto de intersección de dichas rectas sería el punto (-0.5, 1.5). La ubicación del domicilio en dicho punto haría que los miembros de la familia tuvieran que recorrer los tres la misma distancia.

Bibliografía

KRAUSE, E. F., Taxicab Geometry. New York: Dover Pub (1987).