A Boundary Sampling Algorithm for Computing the Voronoi Graph of a 2-D Polygon

Michal Etzion and Ari Rappoport

The Voronoi graph of a set of sites contains the complete symbolic information of the Voronoi diagram of the sites without the latter's geometry. The Voronoi graph is important for two reasons. First, there are applications that need only the symbolic proximity information of a shape, without requiring geometry. Second, the graph can be used as a starting structure for a robust and efficient global or local computation of the Voronoi diagram.

In this paper we present an algorithm that computes the Voronoi graph of a 2-D polygon (with holes) by generating the Voronoi diagram of a finite set of points on the polygon's boundary. Unlike algorithms for computing the Voronoi diagram of a polygon, our algorithm avoids manipulation of non-linear entities and is simple to implement. The operations used by the algorithm are line intersections and comparisons of distances between points and lines.

Technical Report, Institute of Computer Science, The Hebrew University, 1996.