Voronoi diagram and medial axis algorithm for planar domains with curved boundaries. I: Theoretical foundations (Q1300788)

In this first installment of a two-part paper, the authors present the underlying theory for an algorithm that computes the Voronoi diagram and medial axis of a planar domain bounded by free-form (polynomial or rational) curve segments. An incremental approach to computing the Voronoi diagram is used, wherein a single boundary segment is added to an existing boundary segment set at each step. The introduction of each new segment entails modifying the Voronoi regions of the existing boundary segments, and constructing the Voronoi region of the new segment.