Geometry in Action

Voronoi Diagrams

The Voronoi diagram of a collection of geometric objects is a partition of space into cells, each of which consists of the points closer to one particular object than to any others. These diagrams, their boundaries (medial axes) and their duals (Delaunay triangulations) have been reinvented, given different names, generalized, studied, and applied many times over in many different fields. Voronoi diagrams tend to be involved in situations where a space should be partitioned into "spheres of influence", including models of crystal and cell growth as well as protein molecule volume analysis.

3d shape and surface matching. Elias Kalaitzis of Edinburgh uses 3d Voronoi diagrams in an iterated parallel procedure for approximating a geometric transformation aligning a pair of shapes.
Automated derivation of high accuracy road centrelines: Thiessen polygons technique. A. Ladak and R. B. Martinez use Voronoi diagrams to automatically construct maps of the roads in Qatar from databases of nearby buildings.
Case Studies in Biometry. This book by N. Lange and others mentions Voronoi diagrams as a method for detecting clusters of disease incidence.
Cell growth. The Mosaic project at U. Geneva uses Voronoi diagrams as part of a simulation of cell growth, mitosis, and interaction.
Convex hull, Voronoi diagram, and Delaunay triangulation software from Nina Amenta's CG software directory.
Convex hulls and interpolation. Ken Clarkson describes some implementation details of algorithms for convex hulls, alpha shapes, Voronoi diagrams, and natural neighbor interpolation.
Decomposing trimmed surfaces using the Voronoi tesselation, P.-Y. Tsai and B. Hamann, Mississippi State U.
Dirichlet tessellation of bark beetle spatial attack points. J. Byers uses Voronoi diagrams to understand the spatial distribution of insects.
Dynamic segmentation and Thiessen polygons: a solution to the river mile problem. Hargrove, Winterfield and Levine use Voronoi diagrams to construct a coordinate system for locations on water or along other linear structures such as interstate highways.
Grouping words and multi-part symbols. M. Burge and G. Monagan use Voronoi diagrams for document analysis.
Image tilings. The PRISME group at INRIA proposes stitching together multiple images of a scene (e.g. multiple aerial or satellite views of a piece of land) using a form of Voronoi diagram to choose which image has the best quality for each piece of scenery.
Ionic association in electrolyte solutions: A Voronoi Polyhedra analysis, and The Voronoi Polyhedra as tools for structure determination in simple disordered systems. J.C. Gil Montoro and J.L.F. Abascal investigate the use of Voronoi diagrams in analyzing chemical simulations.
Mosaic / stained glass graphic effect. One gets interesting visual effects by taking a random sample of pixels from a bitmap image, computing the Voronoi diagram of the sample, and filling each cell with the corresponding sample's color. This appears to be what Photoshop does in its "Pixelate->Crystalize" filter; it can be thought of as a form of piecewise constant function interpolation.
Navigating in the map. Anton Castro Francois and Chris Gold use Voronoi diagrams to embed users' points of view in maps and enable the users to interact with sets of local features.
Partition based point pattern analysis methods for investigation of spatial structure of various stellar populations, L. Pásztor, ADASS '94.
Percolation. Ted Davis of U. Minn. uses Voronoi diagrams to simulate fluid flow through porous media.
Petroleum reservoir simulation. Santosh Verma of Stanford uses Voronoi diagrams "to accurately represent horizontal and deviated wells, local flow geometry, faults, major heterogeneities, etc" in petroleum reservoir simulation.
Prove protein volume evaluation software. This project at the Free University of Brussels uses Voronoi diagrams and weighted Voronoi diagrams to analyze the portion of a molecule's volume taken up by each atom in the molecule. Mark Gerstein at Stanford has a directory with very similar software and related papers.
Reconstruction of geological data using 3d Voronoi diagrams. From the PRISME project at INRIA.
Riemann surfaces and algebraic curves. Juha Haataja (Ctr. for Scientific Computing, Finland) describes some applications of Voronoi diagrams (aka Dirichlet polygons) in pure mathematics.
Settlement selection for interactive display. How to choose which towns to show on a map, when the scale is too low to show everything? M. van Kreveld, R. van Oostrum, and J. Snoeyink describe algorithms based on incremental maintenance of Voronoi diagrams.
Skeleton and boundary extraction. Glynn Robinson of Yale overlays the Delaunay triangulation and Voronoi diagram of points sampled from a surface (the boundary between different features in a medical image) and somehow extracts from them subsets representing the surface itself and its medial axis.
Soap froth. Lutz Neubert and Michael Schreckenberg of Duisberg use Voronoi diagrams as an initial condition for investigating the evolution of soap bubble froths.
Structure determination in disordered systems. J.C.G. Montoro and J.L.F. Abascal use Voronoi polyhedra to detect clusters in rapidly quenched liquids.
Mihran Tuceryan's computational geometry research page describes an application of Voronoi diagrams to finding neighbor relationships between image tokens, and includes bibliographic references to related papers by Tuceryan, Ahuja, and others.
US Patent 5564004 uses Voronoi diagrams as part of a user interface that highlights the icon nearest the cursor in a windowing system.
Using the Voronoi Tessellation for Grouping Words and Multi-part Symbols in Documents, M. Burge and G. Monagan.
VORAPP-L mailing list for Voronoi and computational geometry applications.
Voronoi.com, tutorials, applications, and implementations of Voronoi methods of spatial analysis.
Voronoi diagram of McDonalds outlets in San Francisco. Demo of a commercial GIS tool.
Voronoi diagrams: from archaeology to zoology. Lecture by Scot Drysdale. Mentions applications in anthropology, archaelogy, astronomy, biology, ecology, forestry, cartography, crystallography, chemistry, finite element analysis, geography, geology, geometric modeling, marketing, mathematics, metallurgy, meteorology, pattern recognition, physiology, robotics, statistics, and zoology.
Voronoi diagrams in biology, Zdravko Jeremic, Benoit College.
Voronoi methods in geomatics. Abstract of a talk by Chris Gold at Carleton U. See also Gold's many papers on Voronoi-diagram based methods in geographic information systems.

Part of Geometry in Action, a collection of applications of computational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.

Semi-automatically filtered from a common source file. Last update: 02 Sep 1999, 20:49:57 PDT.