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

- Spiderweb Microphone, September 9, 2024

- Adornment, September 2, 2024

- Brain Size, August 26, 2024

- Ice Formation, August 19, 2024

- Quantum Year 2025, August 12, 2024

- Plant Sounds, August 5, 2024

- Diophantine Equations, July 29, 2024

- Green Ammonia, July 22, 2024

- Cold Brew Coffee, July 15, 2024

- US Independence Day, July 4, 2024

- Copper and Green Energy, July 1, 2024

- Baseball Mud, June 24, 2024

- Wiedemann-Franz Law, June 17, 2024

- A.I., Wine, and Beer, June 10, 2024

- Bergmann's rule, June 3, 2024

- 60 Hertz Standard, May 27, 2024

- Droplets, May 20, 2024

- Levitation, May 13, 2024

- 100 Years of IBM, May 6, 2024

- Cicada Apocalypse, April 29, 2024

- Critical Materials, April 22, 2024

- Eclipse 2024, April 15, 2024

- Reverse Sprinkler, April 8, 2024

- T Coronae Borealis, April 1, 2024

- Coffee and Tea, March 25, 2024

- Arno Penzias (1933-2024), March 18, 2024

- Wave-Particle Duality, March 11, 2024

- Offshore Wind, March 4, 2024

- High Entropy Ceramics, February 26, 2024

- Methane Emissions, February 19, 2024

- Thales, Heron, and Experimental Mathematics, February 12, 2024

- Mica, February 5, 2024

- Disk Packing, January 29, 2024

- Is e
^{π}> π^{e}?, January 22, 2024

- Brownian Motion Energy Harvesting, January 15, 2024

- Coin Flip, January 8, 2024

### Deep Archive

Deep Archive 2006-2008

**Blog Article Directory on a Single Page**