Computation of Voronoi Diagram of Planar Freeform Closed Convex Curves Using Touching Discs

Voronoi diagram (VD) is an extensively studied geometric entity since it has applications in fields such as computer graphics, computer vision, geometric modeling etc. In this paper, an algorithm for computing the VD of a set of planar freeform closed convex curves has been developed, without approximating the curves using points or lines. Algorithms for VD predominantly lie on computing the bisectors, a geometrically complex and a high degree curve even for inputs of low degree. Hence, a lot of processing is required to compute bisector segments that contribute to VD as well as in the computation of branch points. In this paper, it has been shown that computation of a branch point is possible without first computing either the bisector or segments of it. The algorithm uses the minimum antipodal discs (MADs) for all pairs of curves. Three touch discs (TTD) (circles touching three curves) are computed only for a specific set of three curves. Decision criteria for a TTD to become a branch disc (BD, i.e. empty TTD) have been addressed without using explicit curve containment check. Local computations of Voronoi segments are then done. The algorithm gives all branch points via centers of the branch discs along with the segments of curves that will contribute to VD. Results of implementation are provided along with analysis of the algorithm.