Voronoi diagrams (also known as Dirichlet tesselation or Thiessen polygons) are everywhere in nature. You have encountered them thousands of times, but maybe did not call it this way. Voronoi diagram are simple, yet they have incredible properties which have found applications in fields ranging from cartography, biology, computer science, statistics, archaeology, all way to architecture and arts.
What is a Voronoi diagram?
Suppose you have \(n\) points scattered on a plane, the Voronoi diagram of those points subdivides the plane in exactly \(n\) cells enclosing the portion of the plane that is the closest to the each point. This produces a tessellation that completely covers the plane. As an illustration, in Figure 1, I plotted 100 random points and their corresponding Voronoi diagram. As you can see, every point is enclosed in a cell, whose boundaries are exactly equidistant between two or more points. In other words, all the area enclosed in the cell is closest to the point in the cell than to any other point.
Figure 1: Voronoi diagram from 100 random points in a plane
Voronoi patterns are ubiquitous
Voronoi patterns in nature
The pattern created by Voronoi diagrams is a common one in nature. In Figure 3, I made a small collage of some naturally occurring Voronoi-like patterns. From microscopic cells in onion skins, to the shell of jackfruits and the coat of giraffes. These patterns are everywhere!
A first reason for their omnipresence is that they form efficient shapes. As we mentioned earlier, Voronoi diagram completely tessellates the plan: hence, all space is used. This is very convenient if you are trying to squeeze as much as possible in a limited space — such as in muscle fibres or bee hives. Secondly, Voronoi diagrams are a spontaneous pattern whenever something is growing at a uniform growth rate from separate points (see Figure 2). For instance, this explains giraffe exhibit such patterns. Giraffe embryos have a scattered distribution of melanin-secreting cells, which is responsible for the dark pigmentation of the giraffe’s spots. Over the course of the gestation these cells release melanin — hence spots radiate outward. Interested reader may refer to this paper, in which the authors use Voronoi diagrams to model computer rendering of spots on animals coats.
Figure 2: A Voronoi diagram is obtained from constant outward growth from dispered points
Source: Wikipedia
Figure 3: Voronoi patterns are everywhere in nature.
(From top-left to bottom right: microscope view of onion skin cells, cross-section of a muscle, garlic bulb, wings of a dragonfly, soap bubbles, close-up of a leaf, giraffes coat patterns, corns, jackfruits hanging from a tree.)
Voronoi pattern in architecture and arts
Perhaps because of their spontaneous “natural” look, or simply because of their mesmerising randomness, Voronoi patterns have intentionally been implemented in human-made structures. An architectural example is the “Water cube” built to house the water sports during the 2008 Beijing Olympics. It features Voronoi diagrams on its ceiling and façades (Figure 4). The Voronoi diagrams were chosen because they recall bubbles1. This analogy is very clear at night, when the entire façade is illuminated in blue and comes alive.
Figure 4: Water cube in Beijing
But Chinese appreciation of Voronoi pattern is surely older than this building. Guan and Ge ware from the Song dynasty have a distinctive crackled glaze. Ceramics can easily crack during the cooling process, however the crackles from the Guan and Ge ware are different — they are intentional. They are sought after because of their aesthetic qualities, which makes each piece is unique. The forming of these patterns on the glaze is usually understood as a sequence of cracks affecting successively smaller subsets of the material’s surface. This process, known as hierarchical cracking, often yields patches of patterns similar to Voronoi diagrams. Hence, Voronoi diagram have commonly been used to model these cracking behaviours. To date, this Voronoi-like pattern is one of the most imitated styles in porcelain (Figure 5).
Figure 5: Guan and Ge wares
Voronoi diagrams are also common in graphic arts for creating “abstract” patterns. I think they make excellent background images. For example, I created the thumbnail of this post by generating random points and constructing a Voronoi diagram. Then, I coloured each cell based on the distance of its point from a randomly selected spot in the box (Figure 6). Endless “abstract” backgrounds images could be generated this way.
Figure 6: Coloured Voronoi diagram
Mathematical definition and some interesting properties
So far, we have presented a simple two-dimensional Voronoi diagram. However, the same type of structure can be generalised to an \(n\)-dimensional space. Suppose \(P=\{p_1,p_2,...,p_m\}\) is a set of \(m\) points in our n-dimensional space. Then, the space can be partitioned in \(m\) Voronoi cells, \(V_i\), containing all points in \(\mathbb{R}^n\) that are closer to \(p_i\) than to any other point.
\[V_i = \left\{x : \forall j \neq i, d(x, p_i) \leq d(x,p_j)\right\} \text{, with } i,j \in \{1,2,...,m\}\] Where the function \(d(x,y)\) gives the distance (\(a\)) between its two arguments. Typically, the Euclidean distance is used (\(l^2\) distance):
\[d(x,y)=||x-y||_2=\sqrt{\sum_{k=1}^{n}(x_k-y_k)^2}\] However, Voronoi diagrams could be designed using other distance functions. For instance, Figure 7 shows a Voronoi diagram obtained with the Manhattan or cityblock distance (\(l^1\) distance). The Manahattan distance is the distance between two points if you had to follow a regular grid — such as the city blocks of Manhattan. The result is a more “boxy” Voronoi diagram. \[d(x,y)=||x-y||_1=\sum_{k=1}^{n}{|x_k-y_k|}\]
](manhattan-voronoi2.png)
Figure 8: Comparison of Voronoi diagrams using the Euclidean (left) and Manhattan (right) distance for a same set of points
Source: Wikipedia
Euclidean distance is the most common distance measure in scientific applications of the Voronoi diagram. It also has the advantage of generating Voronoi cells that are convex. That is to say, if you take any two points within a cell, the line that connects the two points will lie entirely within the cell.
Finally, it should also be noted that Voronoi diagrams are tightly linked with the k-nearest neighbours algorithm (k-NN) — a very popular algorithm in classification, regression and clustering problems. The algorithm uses the \(k\) closest examples in the training dataset to make value predictions. Since the Voronoi diagrams partitions the space in polygons containing the closest points to each seed, the edges of Voronoi cells correspond exactly to the decision boundaries of a simple 1-nearest neighbour problem.
Delaunay triangulation
If you take each of the points from a Voronoi diagram and link it with the points in its neighbouring cells, you will obtain a graph called Delaunay triangulation. In mathematical terms, the Delaunay triangulation is the dual graph of the Voronoi diagram. In the Figure below, a Voronoi diagram (black) and Delaunay triangulation (grey) is plotted from a set of points. By moving the mouse over the image, one can explore how they are affected by a new point.
Figure 9: Voronoi diagram and Delaunay triangulation
Source: r2d3
Delaunay triangulation is just as amazing as Voronoi diagrams. As the name suggests, it produces a set of triangles linking our points. These triangles are such that if one were to draw a circle across the vertices of these triangles, there would be no other point inside the circle (See Figure 10). Moreover, Delaunay triangulation also has the property of maximising the smallest angle of in the triangles of the triangulation. Hence, Delaunay triangulation tends to avoid triangles with acute angles.
](the-fascinating-world-of-voronoi-diagrams_files/figure-html5/unnamed-chunk-11-1.png)
Figure 10: Delaunay triangles are constructed such that no point falls inside the circle circumscribing each triangle
Source: Wikipedia
These properties make it very useful in modelling surfaces and objects from a set of points. For instance, the Delaunay triangulation is used to generate meshes for the finite element method and in facial recognition, construct 3D models for computer animations and model terrain in GIS analysis.
Lloyd’s relaxation algorithm
Llyod’s algorithm is a useful algorithm related to Voronoi diagrams. The algorithm consists in repeatedly alternating between constructing Voronoi diagrams and finding the centroids (i.e. center of mass) of each cell (See Figure 12). At each iteration, the algorithm spaces the points apart and produces more homogeneous Voronoi cells.
Figure 11: Steps in Lloyd’s relaxation algorithm
After a few iterations, the cells will already have a “rounder” aspect and points will be more evenly distributed. This is illustrated in the figure below, in which I have plotted the first 30 iterations of the Lloyd’s algorithm for a random set of points. For each point, I also record their starting position (grey hollow circle) to better trace the movement of each cell. For high number of iterations, the diagram tends to converge towards a stable Voronoi diagram in which every seed is also the centroid of the cell — also known as the centroidal Voronoi diagram. Interestingly, in 2D, Voronoi cells will tend to turn into hexagons because they provide the most efficient way of of packing shapes in a plane. As any bee building their hive can certify, hexagonal cells have two big advantages: 1) they ensure no empty space is left between cells (i.e. tessellates the plane), and 2) hexagons offer the highest ratio between surface and perimeter of the cell. This so-called Honeycomb conjecture, took mathematicians two-thousand years to prove.
Figure 12: 30 iterations of the Lloyd’s algorithm
In data science, Lloyd’s algorithm is at the basis of k-means clustering — one of the most popular clustering algorithms. k-means clustering is typically initiated by taking \(k\) random “centroids” in space. Then, data points are grouped in \(k\) clusters by alternating between 1) assigning data points to the closest “centroid” (this is equivalent to building a Voronoi diagram for the centroid and checking which point are inside the cell) and 2) updating the centroid by calculating the mean of the points inside each cell (See Figure 14).
](K-means_convergence.gif)
Figure 13: k-means clustering
Soruce: Wikipedia
Besides data science, Lloyd’s algorithm is used in a variety of applications. For instance, it is very common in quantization and lossy data compression algorithms (e.g. Lloyd-Max algorithm). It is also very useful whenever one wants random points that are nicely spaced. For instance, it could be used to smooth meshes generated from the Delaunay triangulation, for dithering images, or as a basis for procedural maps generation in video games.
How to construct Voronoi diagrams?
One could construct Voronoi diagrams by building each cell one by one. If one extends the bisector of the segments linking every combination of points, it is possible to obtain the outline of Voronoi cells (Figure 15). However, this technique is quite inefficient. Considering there are \(\frac{1}{2}(1-n)n\) combinations of points, the complexity of such algorithm would increase quadratically with the number of points.
](construct-voronoi2.jpg)
Figure 14: Construction of Voronoi cells
Source: Roberto Tamassia
More efficient alternatives have been proposed. For example, the Sweep line algorithm builds Voronoi cells progressively by sequentially using binary search tree and priority queue operations (Figure 16). A good description of this algorithm can be found here. Another way of constructing Voronoi diagrams, is to first build Delaunay triangulations. Once the triangulation is obtained, extending the bisectors of the triangle edges leads to the Voronoi diagram (Figure 17). Delaunay triangulation can be obtained without the need of considering every pair of points. For instance, an efficient technique consists in projecting the points on a paraboloid in a higher dimension. Re-projecting back the convex hull onto the original space gives the Delaunay triangulation (Figure 18)
](construct-voronoi.jpg)
Figure 16: Construction of Voronoi diagrams
Source: Giulia Andreucci
](construct-voronoi-convex.jpg)
Figure 17: Using the convex hull method for constructing Delaunay triangulation
Source: Danny Sleator
A discussion of different algorithms for computing Voronoi diagram and their complexity is available here, here, and here. New algorithms are continuously being proposed to improve computation efficiency in different circumstances (e.g. Yan et al. 2011, Qin et al. 2017). There are also techniques requiring constant time that generate approximate Voronoi diagrams (e.g. Jump flooding algorithm).
Links to additional material
This article tells the story of how Voronoi diagrams were used by John Snow to show the link between water pumps and the transmission of Cholera during the 1854 London outbreak.
Amil Patel has a phenomenal blog on game development. I highly recommend his posts on procedural map generation with Voronoi diagrams.
This post by David Austin gives a great explanation of the Sweep line algorithm for computing Voronoi diagrams.
This nice looking map by Jason Davies is a Voronoi diagram of the location of airports around the world.
Spatial Tessellations: Concepts and Applications of Voronoi Diagrams is a bible on Voronoi diagrams. If you have any doubt about Voronoi diagrams, you will certainly find an answer here.
These slides from Vincent Legat have some beautiful drawings for different construction algorithms.
Voronoi diagrams are commonly used to model trees in forests (e.g. Abellanas et al. 2016, Bohler et al. 2018).
Voronoi diagrams can also be used to determine robot’s paths. Check these articles: article 1, article 2.
Voronoi diagrams have thousand of applications. From modelling trees in a forest to planning robot paths. In this article I barely scratched the surface. These links contain lists of interesting applications: link 1, link 2, link3, link4, link 5.
To be more precise, the “Water cube” patterns are inspired from Weaire-Phelan bubbles. However, these are directly obtainable as Voronoi diagram.↩︎