A Voronoi diagram is a partitioning of a plane constructed as follows:
-
Pick a random number of random points \(P_i\) in the plane.
-
To each \(P_i\) corresponds that part of the plane that is the set of all points that are closer to \(P_i\) than to any other \(P\).
In the above figure, the red partition corresponds to the set of all points that are closest to \(P_1\).