Recognizing Voronoi Diagrams with Linear Programming
David Hartvigsen · INFORMS journal on computing · 1992
Let P = {P 1 , …, P n } be a finite set of distinct points in ℝ d and let R i be the set of points whose distance from P i is less than or equal to the distance from every other point in P. The collection of regions R 1 , …, R n is called the Voronoi diagram generated by P. Our main result is a polynomial time algorithm for recognizing whether or not a given tessellation of ℝ d into polyhedra is a Voronoi diagram. This is accomplished by describing a linear program that has a solution if and only if the given tessellation is a Voronoi diagram. As a consequence, for each R i of a Voronoi diagram, the set of points in R i contained in some generating set P is either a singleton or the interior of a polyhedron. We also give a polynomial time algorithm for describing this set for each R i . Finally, this leads to a second algorithm for recognizing Voronoi diagrams; this algorithm also relies on linear programming but, for fixed dimension d, it is strongly polynomial and has linear time complexity. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.