Voronoi diagrams and medial axes of planar domains with curved boundaries
Rajesh Ramamurthy · 1998
The Voronoi diagram of the boundary of a planar domain is a unique partition of the plane, such that every point within a region formed by the partition is at least as close to one particular boundary segment as it is to all the other boundary segments. The medial or symmetric axis of that domain is the locus of centers of maximum-radius circles (touching the boundary in two points) that can be inscribed within the domain. The edges of the Voronoi diagram/medial axis are either point/curve or curve/curve bisector loci. The a priori computations of Voronoi diagrams and medial axes of planar domains with curved boundaries are useful in a variety of application contexts. Several algorithms, for Voronoi diagram and medial axis constructions, are currently available in the computational geometry literature. However, most of these algorithms are incapable of operating on planar domains with curved boundaries. Algorithms for constructing both Voronoi diagrams and medial axes of domains bounded by polynomial/rational curve segments are developed in this dissertation. These employ algorithms for basic curve/curve bisector constructions, which are also described. The Voronoi diagram of a domain is constructed by an incremental merging scheme, wherein one boundary segment is included at a time, and the existing Voronoi diagram is updated to account for the new boundary segment. The medial axis algorithm, which takes the interior Voronoi diagram as input, removes those edges of the interior Voronoi diagram whose points have a single footprint on the boundary, and then adds the self-bisectors of individual boundary segments. The algorithms are designed to (i) capture all rational segments of the Voronoi diagram and medial axis explicitly; (ii) approximate all other edges, that are high degree algebraic curves having no rational representation, as sequences of parabolic/cubic Bezier curve interpolants, within the prescribed geometric error; and (iii) to remain faithful, within the specified tolerance, to the true topology of the Voronoi diagram/medial axis. Features (i) and (ii) are currently unavailable in any of the existing algorithms.