A brief introduction about this ubiquitous pattern and its applications

Francesco Bellelli

·

Follow

Published in

Towards Data Science

·

10 min read

·

Apr 2, 2022

--

22

Listen

Share

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 the 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.

Voronoi patterns are ubiquitous

Voronoi patterns in nature

The pattern created by Voronoi diagrams is a common one in nature. In Figure 2, 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 plane: 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 3). For instance, this explains why giraffes exhibit such pattern. 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.

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 bubbles. This analogy is very clear at night, when the entire façade is illuminated in blue and comes alive.

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).

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.

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={p1,p2,…,pm} is a set of m points in our n-dimensional space. Then, the space can be partitioned in m Voronoi cells, Vi, containing all points in R^n that are closer to pi than to any other point.

Where the function d(x,y) gives the distance (a) between its two arguments. Typically, the Euclidean distance is used (l2 distance):

However, Voronoi diagrams could be designed using other distance functions. For instance, Figure 8 shows a Voronoi diagram obtained with the Manhattan or cityblock distance (l1 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.

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.

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 in the triangles of the triangulation. Hence, Delaunay triangulation tends to avoid triangles with acute angles.

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, 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 11). At each iteration, the algorithm spaces the points apart and produces more homogeneous Voronoi cells.

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 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.

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 13).

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 generate smooth meshes 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 14). However, this technique is quite inefficient. Considering there are 0.5*(n-1)n combinations of points, the complexity of such algorithm would increase quadratically with the number of points.

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 15). 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. 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.

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.
• Amit 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 based on 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 include 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.

This article was originally published here: