How Tessellations Work


Tiling the Universe: Special Tessellations
This Voronoi tessellation is looking at the photon density of a particular region. Each dot in the cell represents a photon.
This Voronoi tessellation is looking at the photon density of a particular region. Each dot in the cell represents a photon.
Image courtesy NASA

As researchers explored tessellations and defined them mathematically, they identified certain types that excel at solving difficult problems. One popular example is the Voronoi tessellation (VT) also known as the Dirichlet tessellation or the Thiessen polygons.

 A VT is a tessellation based on a set of points, like stars on a chart. Each point is enclosed by a polygonal cell -- a closed shape formed from line segments -- that encompasses the entire area that is closer to its defining point than to any other point. Cell boundaries (or polygon segments) are equidistant to two points; nodes, where three or more cells meet, are equidistant to three or more defining points. VTs can tessellate higher dimensions as well.

The resulting VT pattern resembles the sort of honeycomb a bee might build after an all-night nectar bender. Still, what these cockeyed cells lack in beauty, they more than make up for in value.

Like other tessellations, VTs pop up repeatedly in nature. It's easy to see why: Any phenomenon involving point sources growing together at a constant rate, like lichen spores on a rock, will produce a VT-like structure. Collections of connected bubbles form three-dimensional VTs, a similarity researchers take advantage of when modeling foams.

VTs provide a useful way to visualize and analyze data patterns as well. Closely clustered spatial data will stand out on a VT as areas dense with cells. Astronomers use this quality to aid them in identifying galaxy clusters.

Because a computer processor can build a VT on the fly from point source data and a set of simple instructions, using VTs saves both memory and processing power -- vital qualities for generating cutting-edge computer graphics or for simulating complex systems. By reducing required calculations, VTs open the door to otherwise impossible research, such as protein folding, cellular modeling and tissue simulation.

A close relative to the VT, the Delaunay tessellation also boasts a variety of uses. To make a Delaunay tessellation, begin with a VT, and then draw lines between the cell-defining dots such that each new line intersects a shared line of two Voronoi polygons. The resulting lattice of chubby triangles provides a handy structure for simplifying graphics and terrain.

Mathematicians and statisticians use Delaunay tessellations to answer otherwise incomputable questions, such as solving an equation for every point in space. Instead of attempting this infinite calculation, they compute one solution for each Delaunay cell.

In his Jan. 27, 1921, address to the Prussian Academy of Sciences in Berlin, Einstein said, "As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality." Clearly, tessellated approximations fall short of perfection. Nevertheless, they enable progress by reducing otherwise unwieldy problems to a form manageable by current computation power. More than that, they remind us of the underlying beauty and order of the cosmos.

Related Articles

More Great Links

Sources

  • Conder, M.D.E., G.A. Jones, M. Streit and J. Wolfart. "Galois Actions on Regular Dessins of Small Genera." Feb. 17, 2011. (April 7, 2011)http://www.math.uni-frankfurt.de/~wolfart/Artikel/ConJoStWo.pdf
  • Dereudre, D. and F. Lavancier. "Practical Simulation and Estimation for Gibbs Delaunay-Voronoi Tessellations with Geometric Hardcore Interaction." Preprint submitted to Elsevier June 1, 2010. (April 8, 2011)http://arxiv.org/abs/1005.5620v1
  • Encyclopedia Britannica. "M.C. Escher." Encyclopedia Britannica Online. (April 6, 2011)http://www.britannica.com/EBchecked/topic/192344/MC-Escher
  • Geach, James E.. McGill University Department of Physics. Personal correspondence. April 10, 2011.
  • Geach, James E., David N. A. Murphy, and Richard G. Bower. "4098 Galaxy Clusters to z~0.6 in the Sloan Digital Sky Survey Equatorial Stripe 82." Monthly Notices of the Royal Astronomical Society. Jan. 25, 2011.
  • Grünbaum, Branko. "The Emperor's New Clothes: Full Regalia, G-String, or Nothing?" Mathematical Intelligencer. Vol. 6, No. 4. 1984.
  • Jettestuen, Espen, Anders Nermoen, Geir Hestmark, Einar Timdal and Joachim Mathiesen. "Competition on the Rocks: Community Growth and Tessellation." PLoS ONE. Vol. 5, No. 9. Sept. 30, 2010.
  • Jones, Gareth. School of Mathematics, University of Southampton. Personal correspondence. April 11, 2011.
  • Joyce, David E. "The 17 Plane Symmetry Groups." 1997. (April 7, 2011)http://www.clarku.edu/~djoyce/wallpaper/seventeen.html
  • Lavancier, Frédéric. Université de Nantes, Laboratoire Jean Leray. Personal correspondence. April 11, 2011.
  • Padovan, Richard. "Proportion." Taylor & Francis. 1999.
  • Poupon, Anne. Laboratoire d'Enzymologie et Biochimie Structurales. Personal correspondence. April 9, 2011.
  • Poupon, Anne. "Voronoi and Voronoi-Related Tessellations in Studies of Protein Structure and Interaction." Current Opinion in Structural Biology. Vol. 14. Page 233. 2004.
  • Redenbach, Claudia. Fachbereich Mathematik, Technische Universität Kaiserslautern. Personal correspondence. April 11, 2011.
  • Redenbach, Claudia. "On the Dilated Facets of a Poisson-Voronoi Tessellation." Image Analysis & Stereology. March 2011.
  • Rong, Guodong, et. al. "GPU-Assisted Computation of Centroidal Voronoi Tessellation." IEEE Transactions on Visualization and Computer Graphics. Vol. 17, No. 3. March 2011.
  • Roopun, Anita K., et al. "Temporal Interactions Between Cortical Rhythms." Frontiers in Neuroscience. Vol. 2, No. 2. Page 145. 2008.
  • Schattschneider, Doris. "Perplexing Pentagons." Discovering Geometry Newsletter. Vol. 7, No 1. Spring 1996. (April 6, 2011)http://britton.disted.camosun.bc.ca/jbperplex.htm
  • Schreiber, Tomasz and Christoph Thäle. "Limit Theorems for Iteration Stable Tessellations." Preprint. (April 8, 2011)http://arxiv.org/abs/1103.3960v1
  • Soares-Santos, Marcelle. Fermi National Accelerator Laboratory. Personal correspondence. April 13, 2011.
  • Soares-Santos, Marcelle, et. al. "The Voronoi Tessellation Cluster Finder in 2+1 Dimensions." The Astrophysical Journal. Vol. 727, No. 24. 2011.
  • University of St Andrews, School of Mathematics and Statistics. "Maurits Cornelius Escher." May 2000. (April 4, 2011)http://www-history.mcs.st-andrews.ac.uk/Biographies/Escher.html
  • Watson, D. F. "Computing the n-Dimensional Delaunay Tessellation with Application to the Voronoi Polytopes." The Computer Journal. Vol. 24, no. 2. 1981.
  • Weiss, Volkmar and Harald Weiss. "The Golden Mean as Clock Cycle of Brain Waves." Chaos, Solitons and Fractals. Vol. 18, No. 4. Page 643. 2003.
  • Weisstein, Eric W. "Tessellation." (April 5, 2011)http://mathworld.wolfram.com/Tessellation.html

More to Explore