A parallel algorithm for computing Voronoi diagram of a set of spheres using restricted lower envelope approach and topology matching. (August 2022)

• Record Type: Journal Article
• Authors: Mukundan, Manoj Kumar; Thayyil, Safeer Babu; Muthuganapathy, Ramanathan
• Is Part Of: Computers & graphics. Volume 106(2022)
• Page Start: 210
• Page End: 221
• Publication Date: 2022-08
• Subjects: Voronoi diagram -- Topology matching -- Delaunay graph -- Touching sphere -- Lower envelope -- Parallel algorithm; Computer graphics -- Periodicals; 006.6
• DOI: 10.1016/j.cag.2022.05.017
• Languages: English
• ISSNs: 0097-8493

Abstract

Abstract: We present a parallel algorithm for computing the Voronoi diagram of a set of spheres, S in R 3 . The spheres have varying radii and do not intersect. We compute each Voronoi cell independently using a two-stage iterative procedure, assuming the input spheres are in general position. In the first stage, an initial Voronoi cell for a sphere s i is computed using an iterative lower envelope approach restricted to a subset of spheres L i ⊂ S . This helps to avoid defining the bisectors between all pairs of input spheres and develop a distributed memory parallel algorithm. We use the Delaunay graph of sample points from the input spheres to select the subset L i for computing each Voronoi cell. In the second stage, Voronoi cells obtained from the first stage are matched for updating the subsets. If additional spheres are added to a subset L i, the correctness of the computed vertices is verified with the bisectors of spheres newly added to L i . Results and performance of the algorithm show robustness and speed of the algorithm in handling a large set of spheres. Graphical abstract: Highlights: A parallel algorithm for computing the Voronoi diagram of a set of spheres has been developed and demonstrated. A novel sampling strategy based on Delaunay graph of centre points of spheres has also been proposed. Results show that the algorithm is faster as well as robust, even for a large input set.