Understanding the Voronoi diagram

Part I: The Mathematics behind it

Have you ever been in a situation where you had to quickly find the nearest hospital or supermarket? You would probably whip out your phone and search, and it would point you to the nearest one. Easy! Then again, suppose you are searching for an ideal location for setting up a new service, such as a school — a location far from other schools but close to residential complexes. That is a little more difficult, but both the situations can be resolved with one common mathematical concept — the Voronoi diagram.

Imagine a map divided into cells, each cell covering the region closest to a particular center. Such a map is called a Voronoi diagram, named after Georgy Voronoi, a mathematician born in Ukraine in 1868. He is remembered today mostly for this diagram, also known as a Voronoi tessellation, decomposition or partition. In the school example, a Voronoi diagram can be used to find the largest empty circle amid a collection of points, giving the ideal location for the new school.

Let us try to understand the Voronoi diagram from a mathematical perspective.

Given a finite set of points on a plane, a Voronoi diagram subdivides the plane into cells or regions corresponding to each point such that for any new point within a cell, the nearest neighbour is a point of that cell.

Let us understand this better by visualizing it with an example:

Here all points to the left of the bisector are closer to A while all the points to the right of the bisector are closer to B. Note that all points on the bisector are equidistant from the two points.

Similarly, we can see what happens when a third point is added to the plane and the resulting diagram is an intersection of the individual halfplanes. Then we add a fourth and a fifth and you can see where this goes for even more points.

Thus, for each point, the corresponding Voronoi cell consists of all the locations closer to it than to any of the other points.

The cells are all convex polygons (they have boundaries made up of line segments and all corners have internal angles less than 180 degrees) as they are intersections of halfplanes.

A line segment that is a part of the boundaries between the points can be defined as a Voronoi edge between two points if it is equidistant from those two points and will be farther away from all the other points on the plane.

A Voronoi vertex is the intersection point of corresponding Voronoi edges.

Note: Following our definition of a Voronoi edge, a Voronoi vertex will be equidistant from atleast three points.

A Voronoi diagram can also be seen as a planar graph, with the exception of edges that might go to infinity (which will be dealt with in a later section). And this graph will be a connected graph. The only case where the graph is not connected is when all the points in consideration lie on a single line.

As we can see, the edges never intersect and thus this graph is not connected.

Now that we understand a basic Voronoi diagram and its components, let us take a look at the geometrical complexity of this diagram.

Geometrical Complexity:

First, we take a look at the complexity of a single cell in a Voronoi diagram. For this, we once again review the previous example of a plane with two points, the number of edges that each cell has is one. In a plane with three points, the number of edges for each cell is two and so on. Thus, we notice that for a graph with (n) points, each cell seems to have (n-1) edges.

Note that, due to the positioning of the points, in some cases a cell in an (n) point diagram may have less than (n -1) edges but never more.

So we conclude that a single cell can have (n -1) sides where (n) is the number of points in the diagram.

We now discuss the geometrical complexity of a Voronoi diagram using the planar connected graph definition mentioned before.

We take a look at Euler’s Formula for plane connected graphs. This formula tells us the relation between the vertices, edges and faces of any plane connected graph and is given as –

Where,

V: Number of vertices in the graph

E: Number of edges in the graph

F: Number of faces in the graph (Remember that we count the outer face as well)

Let us consider a simple example -

However, we have trouble applying this formula to a Voronoi diagram when there are edges going to infinity and in order to remedy this we consider an additional virtual vertex — known as point at infinity — which the edges are connected to.

Handshaking Lemma:

In graph theory, a branch of mathematics, the handshaking lemma is the statement that every finite undirected graph has an even number of vertices with odd degree. So what does this mean? It means that given a graph, 2 times the number of edges is the same as the sum of the degrees of the vertices.

Where, (n_e) is number of edges and v represents the vertices.

We have seen that for a graph with at least three non co-linear points, every Voronoi vertex by definition will have a degree of at least 3.

Where (n_v) is the number of voronoi vertices. We add one in order to count the additional vertex i.e. point at infinity.

We can represent Euler’s formula using similar notations as-

It is now easy to simultaneously solve these two equations for finding the bounding conditions on number of Voronoi vertices and number of edges.

Hence, we conclude that a Voronoi diagram of n points in the plane R² has almost (3n — 6) Voronoi edges and (2n — 5) Voronoi vertices.

Therefore,

It is important to know these properties and definitions in order to not only compute or build a Voronoi diagram but to also extract the data required from it. These properties allow us to run more complex queries on our diagrams.

A Delaunay Triangulation is a straight line dual graph of a Voronoi diagram. Once we have the Voronoi diagram, we can easily derive the Delaunay triangulation and do not need to do any complex computation.

Applications:

Now that we understand the various facets of a Voronoi diagram, let us look at some of the applications within the field of computer science, in particular, computational geometry.

• Knuth’s Post Office Problem — Given a set of locations for post offices, you can determine the closest post office to a given house. (Apparently, Knuth was ignoring the existence of ZIP codes.)
• Closest Pair — Given a set of points, you can find the two that are closest together.
• All Nearest Neighbors — Given a set of points, you can find each point’s nearest neighbor.
• You can find the Euclidean Minimum Spanning Tree for a given graph.
• Fixed Radius Near Neighbors — You can find all pairs of points closer than a given distance apart.
• All K Nearest Neighbors — You can find each point’s k closest neighbors.

Now that you know the mathematics behind the Voronoi diagram, check out my next blog to look at an algorithmic approach to compute a Voronoi diagram. Learn more about Fortune’s Algorithm.