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

*Procedure for construction of a Wigner-Seitz cell.1. Draw connecting lines between nearest-neighbors2. 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 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.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, 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.*

### References:

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

Linked Keywords: Student; elementary school; history; classroom; class; randomness; random; memory; France; French; military engineering; military engineer; Pierre Charles L'Enfant (1754-1825); L'Enfant Plan; street plan of the United States Capital; associative memory (psychology); association; child; elephant; French language; diaper; diapered; George Washington; rectangle; rectangular; regular grid; street; diagonal; avenue; traffic circle; plaza; engraving; paper; US Library of Congress; Wikimedia Commons; geometry; geometric; tessellation; tiling with regular polygons; patio; science; scientific; Voronoi tessellation; Bravais lattice; Wigner-Seitz cell; crystal symmetry; physicist; Eugene Wigner; Frederick Seitz; perpendicular; nearest-neighbor; atom; two-dimensional space; three-dimensional space; plane; volume; volumetric; Wigner-Seitz cell; Inkscape; Great Britain; British; physician; John Snow (1813-1858); cholera; water pump; infection; 1854 Broad Street cholera outbreak; simple cubic lattice; hexagonal tiling; Fortune's algorithm; big O notation; Steven Fortune; distinguished member of the technical staff; Bell Labs; algorithm; CGAL, the Computational Geometry Algorithms Library; intuition; intuitive; circle; MATLAB; Euclidean geometry; source code; Jahobr; proprietary software; free and open-source software; C language program; voronoi.c; professional; programmer; Truevision TGA; *.tga image; file format.

### Google Search

Latest Books by Dev Gualtieri

**Previews Availableat Tikalon Press**

*STEM-themed novel for middle-school students*

*Mathematics-themed novel for middle-school students*

*Complete texts of LGM, Mother Wode, and The Alchemists of Mars*

Other Books

- Iron as a Fuel, September 18, 2023

- Cosmic Asymmetry, September 11, 2023

- Work, September 4, 2023

- The Monty Hall Problem, August 28, 2023

- Memristors, August 21, 2023

- Aperiodic Tiling, August 14, 2023

- Fondant Physics, August 7, 2023

- The Gravitational Constant, July 31, 2023

- Length of a Day, July 24, 2023

- Random Walks, July 17, 2023

- Gravitational Lensing, July 10, 2023

- Tiny Bubbles, July 3, 2023

- Thales' Measure of the Sun, June 26, 2023

- Tetrataenite Magnets, June 19, 2023

- Utilitarian Music, June 12, 2023

- Medieval Volcanism, June 5, 2023

- Rare Earths from Bacteria, May 29, 2023

- Georges Lemaitre, May 22, 2023

- Reading Old Manuscripts, May 15, 2023

- The IQ Flynn Effect, May 8, 2023

- Cosmic Water, May 1, 2023

- Warm Whales, April 24, 2023

- Jumping Beans, April 17, 2023

- Gordon Moore (1929-2023), April 10, 2023

- Speed of Light, April 3, 2023

- Amorphous Ice, March 27, 2023

- Curly Hair, March 20, 2023

- Optical Communication, March 13, 2023

- Hygroscopic Energy, March 6, 2023

### Deep Archive

Deep Archive 2006-2008

**Blog Article Directory on a Single Page**