Subject 6.01: Where can I get source for Voronoi/Delaunay triangulation?
For 2-d Delaunay triangulation, try Shewchuk’s triangle program. It includes options for constrained triangulation and quality mesh generation. It uses exact arithmetic. The Delaunay triangulation is equivalent to computing the convex hull of the points lifted to a paraboloid. For n-d Delaunay triangulation try Clarkson’s hull program (exact arithmetic) or Barber and Huhdanpaa’s Qhull program (floating point arithmetic). The hull program also computes Voronoi volumes and alpha shapes. The Qhull program also computes 2-d Voronoi diagrams and n-d Voronoi vertices. The output of both programs may be visualized with Geomview. There are many other codes for Delaunay triangulation and Voronoi diagrams. See Amenta’s list of computational geometry software. The Delaunay triangulation satisfies the following property: the circumcircle of each triangle is empty. The Voronoi diagram is the closest-point map, i.e., each Voronoi cell identifies the points that are closest to an input site. The Voro
