- 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
of disks.
- 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.
- DUST
software for visualization of Voronoi diagrams, Delaunay triangulations,
minimum spanning trees, and matchings, U. Köln.
- Dynamic
formation of Poisson-Voronoi tiles. David Griffeath constructs
Voronoi diagrams using cellular automata.
- Generating
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.
- Paraboloid.
Ray-traced image created to illustrate the
lifting transformation
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
individual-group relations.
Additional Voronoi-based art is included in his
dynamic
systems series.
- Voronoi
diagram of a Penrose tiling (rhomb version), Cliff Reiter.
- Voronoi
diagrams at the Milwaukee Art Museum. Scott Snibbe's
artwork Boundary Functions,
as blogged by Quomodumque.
- Voronoi diagrams of lattices.
Greg Kuperberg
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
necessarily find
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.) - Voronoi
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.
See also
Crispy's
Voronoi game applet
and Dennis
Shasha's Voronoi game page.

From the Geometry Junkyard,
computational
and recreational geometry pointers.

Send email if you
know of an appropriate page not listed here.

David Eppstein,
Theory Group,
ICS,
UC Irvine.

Semi-automatically
filtered
from a common source file.