Voronoi Diagrams
Selected References

Books

Spatial Tessellations: Concepts and Applications of Voronoi Diagrams by Okabe, Boots and Sugihara, John Wiley & Sons, 1992.
This is the bible. Definitions, properties, algorithms, generalizations and applications galore! Unfortunately, it retails for $180. The King County Library System has one copy. There are several copies scattered among academic libraries in the Pacific Northwest, which you can get on interlibrary loan.


Computational Geometry in C by J. O'Rourke, Cambridge University Press, 1994.
Nice senior-level treatment that includes several applications and describes how Voronoi diagrams are related to minimal spanning trees and traveling salesman problems. There is a brief discussion of the "cone slicing" interpretation of Voronoi diagrams. You don't have to know C (or any programming at all) to read this book.


Computational Geometry: Algorithms and Applications by de Berg, van Kreveld, Overmars and Schwarzkopf, Springer-Verlag, 1997.
High-level undergraduate or low-level graduate textbook. Limited, but readable, description of the structure of algorithms for computing Voroni diagrams. You can download the fifteen-page chapter on Voroni diagrams from a web site devoted to this book: http://www.cs.ruu.nl/geobook/

Web sites

http://www.ics.uci.edu/%7Eeppstein/gina/scot.drysdale.html
Long list of applications. Definitions. Some variations of the basic Voronoi problem. Brief description of two algorithms for constructing Voronoi diagrams.


http://www.beloit.edu/~biology/zdravko/voronoi.html
The creation of Zdravko Jeremic as part of the Howard Hughes Young Scholar Program at Beloit College. A little history. Definitions. Tons of references and pointers. Jeremic's paper on modeling animal territories.




Articles

"Dirichlet Polygons - An Example of Geometry in Geography" by T. O'Shea, The Mathematics Teacher, March, 1986.
This is the only non-technical, immediately accessible journal article we could find. It contains a couple of nice, elementary applications.













|Mathographies and Snippets |Math Homepage|