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