Recognizing Voronoi Diagrams with Linear Programming

Let P = {P₁, …, 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₁, …, R_n is called the Voronoi diagram generated byP. 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.