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.
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 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.)