Geometry in Action: Voronoi Diagrams

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.
Applications of Voronoi Tesselations to Tumour Cell Diagnosis, Lynne Dunckley.
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.
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.
Der Technik hinter dem Mühlentag (in German). Kasper Schiess uses Voronoi diagrams to set up web page image maps of geographical locations in such a way that clicking on any point in the map leads to a description of the nearest location.
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.
Floating Points. Deussen, Hiller, van Overveld, and Strothotte use Voronoi diagrams to place stipple points for non-photorealistic rendering.
Somnath Ghosh uses Voronoi diagrams as part of a system for quantitative metallography.
The Green Island Formation in Forest Fire Modeling with Voronoi Diagrams, Roque and Choset, CGC98.
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.
Modeling of microstructures by Voronoi cells. M. Nygärds and P. Gudmundson use the grain structure of a randomly generated Voronoi diagram with periodic boundary conditions to model ferrite/pearlite steel.
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.
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.
Protein secondary structure assignment through Voronoi tesselation, Dupuis, Sadoc, and Mornon.
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.
Qhull software for convex hulls, Delaunay triangulations, Voronoi diagrams, and halfspace intersection about a point.
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.
Sity. Tom Kelly appears to be creating artificial cityscapes by using Voronoi diagrams of sites with lots of collinearity to form the city blocks and streets, similar Voronoi diagrams within the blocks to form property boundaries and building floorplans, and straight skeletons for the rooflines.
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.
Spherulites, a crystal growth formation closely related to Voronoi diagrams and arising in modeling of geological materials, vitamins and red blood cells, and thermoplastics.
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.
Voronoi.com, tutorials, applications, and implementations of Voronoi methods of spatial analysis.
Voronoi, Dutch-language web site dealing with Voronoi diagrams.
Voronoi Art. Scott Sona Snibbe uses a retro-reflective floor to display the Voronoi diagram of people walking on it, exploring notions of personal space and individual-group relations. Additional Voronoi-based art is included in his dynamic systems series.
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.
The Wigner-Seitz method for modeling electron flow in metals by using Voronoi cells of the crystal lattice.