Computation of Voronoi Diagrams and Delaunay Triangulation via Parametric Linear Programming

This note illustrates how Voronoi diagrams and Delaunay triangula- tions of point sets can be computed by applying parametric linear pro- gramming techniques. We specify parametric linear programming prob- lems that yield the Delaunay triangulation or the Voronoi Diagram of an arbitrary set of points S in Rn.