Edge-tracing algorithm for Euclidean Voronoi diagram of 3D spheres
Deok‐Soo Kim, Youngsong Cho, Donguk Kim · Canadian Conference on Computational Geometry · 2004
Despite of many important applications in various disciplines from sciences and engineering, Voronoi diagram for spheres in a 3-dimensional Euclidean distance has not been studied as much as it deserves. In this paper, we present an edge-tracing algorithm to compute the Euclidean Voronoi diagram of 3-dimensional spheres in O( ) in the worst-case, where is the number of edges of Voronoi diagram and is the number of spheres. As building blocks for the algorithm, we show that Voronoi edges are conics and they can (b)