Voronoi diagram is one of the most sought-after geometric structures, and its applications can be found in image segmentation and feature extraction, motion planning, collision avoidance, determining the optimal deployment of infrastructure in town planning, mesh generation, dimensional reduction, surface reconstruction, etc. For a set of geometric entities (such as points, lines, curves, or surfaces), the Voronoi diagram can be considered as the locus of a point equidistant from more than one entity. A Voronoi diagram tessellates the space into regions called Voronoi cells such that there is a Voronoi cell corresponding to every entity in the given set. Each Voronoi cell is a collection of points nearest to the corresponding geometric entity than any other entity in the given set.

We present algorithms for computing the Voronoi diagram of circles in 2D; and spheres in 3D. The proposed algorithms accurately compute the Voronoi diagram of circles and that of spheres with coarse sample points. The use of touching disc and touching sphere has helped increase the performance of the algorithm by avoiding calculations based on computationally expensive bisector intersections. We also present the effectiveness of implementing our algorithms in parallel with a distributed memory.