Nearest Neighbors and Voronoi Diagrams
- Delaunay and regular triangulations.
Lecture by Herbert Edelsbrunner, transcribed by Pedro Ramos and Saugata
Basu. The regular triangulation has been popularized by Herbert as the
appropriate generalization of the Delaunay triangulation to collections
- Delaunay triangulation and points of
intersection of lines. Tom McGlynn asks whether the DT of a line
arrangement's vertices must respect the lines; H. K. Ruud shows that the
answer is no.
- Distances on
the surface of a rectangular box, illustrated using colored wavefronts
in this Java applet by Henry Bottomley.
- Distinct point set with the same distance multiset.
From K. S. Brown's Math Pages.
software for visualization of Voronoi diagrams, Delaunay triangulations,
minimum spanning trees, and matchings, U. Köln.
formation of Poisson-Voronoi tiles. David Griffeath constructs
Voronoi diagrams using cellular automata.
Fractals from Voronoi Diagrams, Ken Shirriff, Berkeley and Sun.
- Interactive Delaunay triangulation and Voronoi diagrams:
VoroGlide, Icking, Klein, Köllner, Ma, Hagen.
D. Watson, CSIRO, Australia.
Baker et al., Brown U.
Paul Chew, Cornell U.
- Mormon computational geometry.
- My face on a Voronoi Diagram.
- Natural neighbors.
Dave Watson supplies instances where shapes from
nature are (almost) Voronoi polygons. He also has a page
of related references.
Ray-traced image created to illustrate the
used to relate Delaunay triangulation
with convex hulls in one higher dimension.
- Realizing a
Delaunay triangulation. Many authors have written Java code for computing
Delaunay triangulations of points. But Tim Lambert's applet does the
reverse: give it a triangulation, and it finds points for which that
triangulation is Delaunay.
- Traveling salesman problem and Delaunay
graphs. Mike Dillencourt and Dan Hoey revisit and simplify some
older work showing that the traveling salesman tour of a point set need
not follow Delaunay edges.
- 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
Additional Voronoi-based art is included in his
diagram of a Penrose tiling (rhomb version), Cliff Reiter.
diagrams at the Milwaukee Art Museum. Scott Snibbe's
artwork Boundary Functions,
as blogged by Quomodumque.
- Voronoi diagrams of lattices.
discusses an algorithm for constructing the Voronoi cells in a planar
lattice of points. This problem is closely related to some important
number theory: Euclid's algorithm for integer GCD's, continued
fractions, and good approximations of real numbers by rationals.
Higher-dimensional generalizations (in which the Voronoi cells form
zonotopes) are much harder -- one can find a basis of
short vectors using the well-known LLL algorithm, but this doesn't
the vectors corresponding to Voronoi adjacencies. (In fact, according
to Senechal's Quasicrystals and Geometry, although the set
of Voronoi adjacencies of any lattice generates the lattice, it's not
known whether this set always contains a basis.)
diagrams and ornamental design.
- The Voronoi Game.
Description, articles, references, and demonstration applet on
problems of competitive facility location, where two players place
sites in hopes of being nearest to as much area as possible.
Voronoi game applet
Shasha's Voronoi game page.
From the Geometry Junkyard,
and recreational geometry pointers.
Send email if you
know of an appropriate page not listed here.
from a common source file.