期刊
COMPUTERS & GRAPHICS-UK
卷 106, 期 -, 页码 210-221出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cag.2022.05.017
关键词
Voronoi diagram; Topology matching; Delaunay graph; Touching sphere; Lower envelope; Parallel algorithm
We propose a parallel algorithm for computing the Voronoi diagram of a set of spheres with varying radii. The algorithm uses a two-stage iterative approach to compute each Voronoi cell independently and optimize the computation by utilizing an iterative lower envelope method restricted to subsets of spheres. Experimental results demonstrate the robustness and efficiency of the algorithm.
We present a parallel algorithm for computing the Voronoi diagram of a set of spheres, S in R3. 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 si is computed using an iterative lower envelope approach restricted to a subset of spheres Li subset of 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 Li 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 Li, the correctness of the computed vertices is verified with the bisectors of spheres newly added to Li. Results and performance of the algorithm show robustness and speed of the algorithm in handling a large set of spheres.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据