09 Mar Voronoi polygons – part I

09/03/2022

If we draw a set of points p_j {p₁, …, p_n} on a flat surface, said surface can be partitioned into the same number of polygons R_j {R₁, …, R_n} fulfilling the condition that all the points x inside the polygon R_k are closer to point p_k than to any of the other p_j. These polygons are also called cells.

Expressed algebraically, R_k = { x∈X | d(x, p_x) ≤ d(x, p_j) for Ɐ j≠k }

In the image on the left, the Voronoi polygons (cells) corresponding to the 22 players on a soccer field are represented. The green polygons correspond to the players of one team and the brown ones to those of the opposite team. If the ball is inside the Voronoi polygon of a player, he will be in advantage to arrive before any other rival.

For the particular case of sets of points p_j equidistant from each other, the Voronoi polygons have the form of regular hexahedrons.

The image on the right shows the system devised in the Comuna de Las Condes in Santiago de Chile to maintain distances between pedestrians waiting on the sidewalk to cross at the zebra crossing. The green traces would represent the points p_j and the white hexagons the limits of the cells R_j. If everyone is located in the center, they will stay equidistant from each other, reducing the chances of viral spread.

The theory is simple and the practice too; software such as QGIS allow the calculation and representation of an unlimited number of polygons associated with the corresponding reference points.

For example, we could represent the Voronoi polygons covering the entire land surface associated with all urban centers, represented by a point. In a future news we will see its use for the location of substations and antennas for 5G telecommunications.

For more information, contact Daniel Sánchez Castán (dsanchez@ingenieros-im3.com)