Hierarchical planar voronoi diagram approximations.

Abstract

Abstract We present a new approach for constructing a polygonal approximation, at a prefixed level of detail, of a planar Voronoi diagram valid for generalized sites (points, line-segments, curve-arc segments,...) and for different distance functions (Euclidean metrics, convex distance functions,...). The approach is based on two related algorithms. The first algorithm constructs a quadtree-based Voronoi diagram codification, the Voronoi-Quadtree. The second algorithm, taking as input the Voronoi-Quadtree, provides a DCEL representation of the approximated Voronoi region boundaries associated to the Voronoi-Quadtree. 1 Introduction The generalized Voronoi diagram [1] of a set of sites partitions the plane into regions, one per site, such that all points in a region have the same closest site according to some given distance function. Voronoi diagrams are widely used in many scientific fields and application areas, such as computer graphics, geometric modeling, geographic information systems, visualization of medical datasets, pattern recognition, robotics, shape analysis or crystal and cell growing, just to name a few (see [10]).