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
nonphotorealistic 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 multipart 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 Multipart Symbols in
Documents, M. Burge and G. Monagan.
 Voronoi.com, tutorials,
applications, and implementations of Voronoi methods of spatial
analysis.
 Voronoi,
Dutchlanguage web site dealing with Voronoi diagrams.
 Voronoi Art.
Scott Sona Snibbe uses a retroreflective floor to display the Voronoi
diagram of people walking on it, exploring notions of personal space and
individualgroup relations.
Additional Voronoibased 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 Voronoidiagram based methods in geographic
information systems.
 The
WignerSeitz method for modeling electron flow in metals
by using Voronoi cells of the crystal lattice.
Part of
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Semiautomatically
filtered
from a common source file.