What is a Voronoi diagram?

When the Fry Building was being designed as the new home for the School of Mathematics, we wanted to build in public art connected with our subject. We decided to commission a specially-designed brise-soleil, or sunscreen, for our new glass atrium.

Voronoi diagrams were considered as early as 1644 by philosopher René Descartes and are named after the Russian mathematician Georgy Voronoi, who defined and studied the general n-dimensional case in 1908.

This type of diagram is created by scattering points at random on a Euclidean plane. The plane is then divided up into tessellating polygons, known as cells, one around each point, consisting of the region of the plane nearer to that point than any other. Our Voronoi pattern was in fact constructed from a set of three-dimensional points, dividing space into polyhedra. If you slice through the polyhedra you see a two-dimensional pattern of polygons, and it was this that was used to create the screen.

Voronoi diagrams have numerous applications across mathematics, as well as in various other disciplines, such as modelling animal territories or crystal growth. In the 1854 London cholera epidemic, physician John Snow used a Voronoi diagram created from the locations of water pumps, counting the deaths in each polygon to identify a particular pump as the source of the infection.

They are also known as Dirichlet patterns, or tessellations, and the cells are also known as Thiessen polygons.

Early in his career, Bristol’s Professor Peter Green devised an algorithm to compute Voronoi diagrams efficiently, which can be applied to very large sets of points. The paper has been cited over 1000 times, by researchers in the analysis of spatial data, for spatial interpolation and smoothing, image registration, digital terrain modelling, epidemic and ecological modelling, in material science, geographical information systems, and in many other areas of science and technology. You can read his paper for more information: Computing Dirichlet tessellations in the plane (with R. Sibson), Computer Journal, 21, 168–173 (1978).

Watch our screen being installed into place on the side of the glass atrium

Edit this page