Muthuganapathy Ramanathan

This paper proposes a unified approach towards computing geometry structures viz. Voronoi diagram, medial axis, Delaunay graph and α-hull of planar closed curves. It initially presents an algorithm for computing the Voronoi diagram of a set of planar freeform closed curves without approximating the curves using points, lines or biarcs. The algorithm starts by computing the minimum antipodal discs (MADs) for all pairs of curves and these MADs are systematically processed to identify all branch points. The key feature of the algorithm is that it computes a branch point without computing any of the bisectors a priori. Local computations of Voronoi segments are then done using the identified pairs of the segments of curves. The theoretical foundation of the algorithm has been first laid for a set of convex curves and then extended to non-convex curves. It has also been shown that the developed algorithm for the Voronoi diagram can also be used to compute related structures such as medial axis, Delaunay graph and α-hull. They have also been addressed without computing Voronoi edges/segments. Results of the implementation have been provided along with a detailed discussion of the algorithm.

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. © 2013 IEEE.