A unified approach towards computing Voronoi diagram, medial axis, Delaunay graph and α-hull of planar closed curves using touching discs. (June 2020)

• Record Type: Journal Article
• Authors: Sundar, Bharath Ram; Mukundan, Manoj Kumar; Muthuganapathy, Ramanathan
• Is Part Of: Computers & graphics. Volume 89(2020)
• Page Start: 131
• Page End: 143
• Publication Date: 2020-06
• Subjects: Voronoi diagram -- medial axis -- Delaunay graph -- α-hull -- freeform curves -- bisectors -- antipodal distance -- touching disc; Computer graphics -- Periodicals; 006.6
• DOI: 10.1016/j.cag.2020.05.010
• Languages: English
• ISSNs: 0097-8493

Abstract

Highlights: A unified algorithmic approach for computing the Voronoi diagram, medial axis, Delaunay graph and α -hull for a set of planar curves. No pre-processing required in approximating the input curve(s). No post-processing required in computing the Voronoi segment(s). Identifying branch points without computing the bisectors greatly reducing the computational complexity. Graphical abstract: Abstract: 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.