Edge-tracing algorithm for Euclidean Voronoi diagram of 3D spheres

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)