Voronoï Diagrams: Part 1 — Simple Analysis
A while ago, I became interested in Voronoï Diagrams because they have a wide range of applications while being relatively easy to understand.
Definition
A Voronoï Diagram is a simple partition of the plan: given a set of n points - often referred to as seeds or sites — you want to create n regions of the plan, one for each point. Those regions are formed such as for each site, any point inside its region is closest to that site than any other site.
In this example, you can see multiple coloured regions, and inside each area, you can spot its seed, a single black pixel. When looking at the diagram, it’s easier to understand how each region is constructed.
Simple Usage Example
A simple usage example is the Post Office problem: imagine your city, with every post office pinned on it, and you want to know the area of attraction of each office. Considering for simplification that people will always come to the post office closest to where they live, the areas of attraction will form a Voronoi Diagram.
Naïve implementation
If you wanted to generate the Voronoi diagram of a set of sites programmatically, a naive implementation would be to iterate through all points of your plan, find the closest site, and add the current point to its region.
In pseudo-code, it would look like this:
It works well, but if you have a large number of points, the execution time quickly goes out of hand, as it has quadratic complexity.
Another problem with that implementation is that you only have information about what’s inside each region. If you needed information about borders, you wouldn’t be able to get it this way.
Case study
Before diving into a better algorithm, let’s study what the Voronoi looks like in some easy cases.
Voronoi Diagram of 1 point
If you only input one seed, there is only one unbounded region to the entire plan.
Voronoi Diagram of 2 points
When you have 2 points, each point gets a region corresponding to half the plan. If a region contains all the points closer to the region’s seed than to any other region, the separation between the two regions consists of points that are neither closer to the point on the left than from the point on the right. Meaning the separation consists of points equidistant from A and B. More precisely, the separation is the bisector of segment AB.
Particular case: Voronoi Diagram of n collinear points
Similarly, if you input n points, all collinear, the Voronoi Diagram will consist of n regions, separated by n-1 parallel lines, all corresponding to the consecutive bisectors.
Voronoi Diagram of 3 points
When you have three non-collinear points, you get three regions that concur in one vertex. We know that each separation consists of points equidistant from their neighbouring sites. When three or more separation meet, it creates a vertex. That vertex is, by definition, still equidistant to the two neighbouring points of the first separation and equidistant to the two neighbouring sites of all other separations that converge to the vertex. That vertex is consequently equidistant to all its neighbouring sites. Which also means it is the circumcenter of the adjacent sites.
Voronoi Diagram of 4 points or more
Starting at 4 points, you begin seeing cases where you get closed regions. Meaning the region is constituted only of segments; there is no infinite line or half-line. For instance, when you have a triangle and put a 4th point inside that triangle.
Definitions
To close off this first article, let’s wrap up what we just observed and bring up some valuable definitions, so we’ll be on the same page for the following up.
Voronoi Edges
The borders of the Voronoï Diagram, also called Voronoi Edges, are points that are strictly between two sites, which means that the boundary between sites A and B is the bisector of segment AB.
Voronoi Vertices
A point where three or more Voronoi Edges meet is called a Voronoi Vertex. As a vertex is the point of convergence of multiple edges, which are bisectors, a is equidistant from all its neighbouring sites. As such, a Voronoi Vertex is the circumcentre of the sites of every one of its adjacent regions.
Conclusion
That’s it for the first part; I hope this gave you a clearer understanding of the magic of Voronoï diagrams. In the following article, we’ll start investigating a better algorithm to compute those diagrams: the Fortune’s algorithm, or more accurately, a variant inspired by Fortune’s work. Stay tuned!
