A Boundary Sampling Algorithm for Computing
the Voronoi Graph of a 2-D Polygon
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.