Voronoi polygons – part I


If we draw a set of points pj {p1, …, pn} on a flat surface, said surface can be partitioned into the same number of polygons Rj {R1, …, Rn} fulfilling the condition that all the points x inside the polygon Rk are closer to point pk than to any of the other pj. These polygons are also called cells.

Expressed algebraically, Rk = { xX | d(x, px) d(x, pj) for jk }

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 pj 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 pj and the white hexagons the limits of the cells Rj. 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)