Los polígonos de Voronoi – parte I

09/03/2022

Si en una superficie plana dibujamos un conjunto de puntos pj {p1, …, pn}, dicha superficie se puede particionar en el mismo número de polígonos Rj {R1, …, Rn} cumpliendo con la condición de que todos los puntos x dentro del polígono Rk son más cercanos al punto pk que a cualquiera de los otros pj. Estos polígonos también se denominan celdas.

Expresado algebraicamente, Rk = { xX | d(x, px) d(x, pj) para jk }

En la imagen de la izquierda se representan los polígonos (celdas) de Voronoi correspondientes a los 22 jugadores en una cancha de futbol. Los polígonos verdes corresponden a los jugadores de un equipo y los marrones a los del contrario. Siempre que el balón esté dentro del polígono de Voronoi de un jugador, éste estará en ventaja para llegar antes que cualquier otro rival.

Para el caso particular de conjuntos de puntos pj equidistantes entre ellos, los polígonos de Voronoi tienen la forma de hexaedros regulares.

En la imagen de la derecha se muestra el sistema ideado en la Comuna de Las Condes de Santiago de Chile para mantener las distancias entre los peatones esperando en la acera para cruzar por el paso de cebra. Las huellas verdes representarían los puntos pj y los hexágonos blancos los límites de las celdas Rj. Si todos se ubican en el centro, se mantendrán equidistantes entre sí, reduciendo las probabilidades de propagación viral.

La teoría es simple y la práctica también; softwares como el QGIS permiten el cálculo y representación de un número ilimitado de polígonos asociados a los correspondientes puntos de referencia.

Por ejemplo, podríamos representar los polígonos de Voronoi cubriendo toda la superficie terrestre asociados a todos los núcleos urbanos, representados por un punto. En una próxima noticia veremos su uso para ubicación de subestaciones y antenas para telecomunicaciones 5G.

Para más informaciones, contactar con Daniel Sánchez Castán (dsanchez@ingenieros-im3.com)