Lately, I have come across an interesting concept in Geometry called Voronoi Polygons (https://en.wikipedia.org/wiki/Voronoi_diagram).
Below is an example (using R programming with code from https://r-charts.com/part-whole/voronoi-diagram/) in which we start of with a set of points (in 2 Dimensions) and Voronoi Polygons are drawn around each point:
# install.packages("deldir")
library(deldir)
# Data
set.seed(1)
x <- runif(50)
y <- runif(50)
# Calculate Voronoi Tesselation and tiles
tesselation <- deldir(x, y)
tiles <- tile.list(tesselation)
plot(tiles, pch = 19,
fillcol = hcl.colors(50, "Purple-Yellow"))
My Question: I am trying to understand in general - given these points, how exactly are the Voronoi Polygons created?
I have seen videos online (https://www.youtube.com/watch?v=q-Ya01iGO0E) that liken this to "soap bubbles forming in a cup of water" - an animation was shown that a small circle is drawn around each point ... and then the circles are expanded in size until they start to collide with each other ... and somehow, this produces a Voronoi Diagram.
But I was hoping to understand this from a more mathematical perspective.
Can someone please help me understand this - given a set of points, how do exactly do you draw a Voronoi Diagram? Is the Voronoi Diagram for any set of points unique?
Thanks!
References:
Voronoi Diagrams are nothing but assigning a Data Point to every Point in the Plane (2D Case , Illustrative Example)
When we say "assigning a Data Point" , it could be a number or a category or a colour. The Examples I give will use Colour.
The assignment is based on "Closeness" , according to some Distance metric , which can be Euclidean Distance or Manhattan Distance or something else. The Examples I give will use Euclidean Distance which is quite usual.
Using colour & Euclidean Distance will make it easy to visualize the Procedure Intuitively.
Let our Data Points be $P=\{A,B,C,D\}$
We will iteratively & manually add the Points to the Plane. Here is the Initial Colouring , where all Points are assigned to Point $A$ & given colour red :
When we include Point $B$ , we see that the Perpendicular Bisector of $AB$ is the line which indicates whether a Point on the Plane is closer to $A$ or to $B$.
Hence , we assign Points closer to $B$ the colour blue.
When we include Point $C$ , we have to check the Perpendicular Bisectors of $AB$ & $BC$ & $AC$ to assign the new colour green.
When we add in the last Point $D$ , we have to check the Perpendicular Bisectors of $AB$ & $BC$ & $AC$ & $AD$ & $BD$ & $CD$ & assign the new colour orange. Most of the lines at long Distances will not matter , except at the Parts close to the newly added Point.
We have the Voronoi Diagram for $P$.
Let us say we have a new Point $E$ towards the right.
Same Procedure will give the new colour lavender to Point $E$.
Calculation & Diagram will change when the new Point $E$ is not at the right , but is at the Centre , like this :
We can continue this manually , though it will quickly get tough when we have Dozens or Hundreds or Millions of Data Points in $P$.
We can automate it with various tools which will use the Distance metric to "draw" the Perpendicular Bisectors (or something else , suitable for that Distance metric) to generate the Voronoi Diagram.
That was all about Intuition & visualization. Here is the "Semi-formal" Definition from Wolfram [[ https://mathworld.wolfram.com/VoronoiDiagram.html ]] :
Similarly , this is the "Semi-formal" Definition from Thomas M. Liebling and Lionel Pournin [[ https://www.math.uni-bielefeld.de/documenta/vol-ismp/60_liebling-thomas.pdf ]] :