Tikalon Header

Voronoi Tessellation

December 18, 2017

Students are taught much "useless information" while in elementary school, most of which is concentrated in history classes. Nearly all of these facts are forgotten; but, for some reason, a few random facts linger in the dark recesses of memory. For example, I remember that the French military engineer, Pierre Charles L'Enfant (1754-1825), was responsible for the street plan of the United States Capital.

As most people, I memorize facts by association. In this case, the association for a child was easily formed, since the name, "L'Enfant," looks as if it should be pronounced like "elephant." If I had known a little more French at the time, the association might have been different, perhaps a diapered George Washington. L'Enfant's plan had the familiar rectangular grid layout of the streets with some diagonal avenues that intersected some grid points at circles and plazas.

L'Enfant's plan for the  area of the US Capitol

L'Enfant's plan for the area near the US Capitol building. A March, 1792, engraving on paper from the US Library of Congress, via Wikimedia Commons


Any division of a plane with geometric shapes such as this is a tessellation. The most common tessellation is tiling with regular polygons, as exists in many patios. However, a common tessellation in scientific studies is the Voronoi tessellation, one example of which is the decomposition of a lattice into Wigner-Seitz cells.

Wigner-Seitz tessellation, used in the analysis of crystal symmetry, is named after physicists, Eugene Wigner and Frederick Seitz. The construction of this tessellation is quite simple. You just draw perpendicular lines at the midpoints of the lines that connect nearest-neighbor atoms, as shown in the figure. Such a construction isn't limited to two dimensions. In a three-dimensional lattice, you can just as easily construct planes at the midpoints to get a volumetric cell.

Wigner-Seitz cell construction

Procedure for construction of a Wigner-Seitz cell.

1. Draw connecting lines between nearest-neighbors

2. Construct perpendicular lines at the midpoints.

3. The area bounded by these lines is a Wigner-Seitz cell.

(Created using Inkscape)


One interesting example of Voronoi tessellation is the study done in 1854 by the British physician, John Snow (1813-1858) who partitioned an area of cholera outbreak. He created this tessellation around individual public water pumps, so the generated cells represented the areas closest to each pump. In this fashion, he isolated the source of the infection to a particular public pump at Broad Street.

Since a Voronoi cell is defined as all points that are closer to the cell focus point than any other focus point, it's easily seen that a Voronoi tessellation of a two-dimensional simple cubic lattice results in a hexagonal tiling (see figure).

Voronoi tessellation of a simple cubic lattice

Voronoi tessellation of a two-dimensional simple cubic lattice, resulting in a hexagonal tiling.

(Created using Inkscape)


One method of creating a Voronoi tessellation deserves special mention. That's Fortune's algorithm, an efficient method devised in 1986 by Steven Fortune, a distinguished member of the technical staff at Bell Labs.[1] His algorithm, and several others, are hosted on CGAL, the Computational Geometry Algorithms Library web site.[2]

Fortune's algorithm, while efficient, is not intuitive. A more understandable approach is to generate expanding circles around the focus points that bump up against each other. This approach is nicely illustrated in the following figure that was generated using MATLAB.

Voronoi tessellation created by Euclidian growth

Voronoi tessellation created by Euclidian growth.

The MATLAB source code for creation of this demonstration image can be found here.

(Wikimedia Commons image by Jahobr, a prolific contributor to Wikimedia Commons)


MATLAB is proprietary software. Since I'm an advocate of free and open-source software, and I needed a little coding practice, I decided to write a C language program to accomplish Voronoi tessellation using this expanding circles approach (source code here.) Since I'm not a professional programmer, this code most certainly could be improved, but it produces the desired result.

The program outputs a *.tga image, a file format chosen because it's easy to implement. The following image is a honeycomb generated from a simple cubic lattice.

Voronoi tessellation on a simple cubic grid

Voronoi tessellation on a simple cubic grid, as generated by my C language program.


The following are two Voronoi tessellations generated from random focus points.

Voronoi tessellations generated from random focus points

Voronoi tessellations generated from random focus points.


References:

  1. S. Fortune, "A sweepline algorithm for Voronoi diagrams," Algorithmica, vol. 2 (November, 1987), p. 153ff., https://doi.org/10.1007/BF01840357.
  2. Voronoi Diagrams section of the Computational Geometry Algorithms Library.