A parallel algorithm for computing Voronoi diagram of a set of circles using touching disc and topology matching

We present a parallel algorithm for computing the Voronoi diagram of a set of circles, C. The algorithm starts with a parallel computation of the Voronoi cell of each circle ci∈C, using a subset of circles, Ci⊂C, and a reduced touching disc method. Unlike the actual touching disc method, a reduced touching disc method does not compute antipodal discs (ADs) between all pairs of circles. We employ the Delaunay graph, D, of the center points of circles in C to set an initial Ci. For computing an initial Voronoi cell for ci∈C, it is enough to compute ADs between ci and each of the circles cj∈Ci. Computation of Voronoi cells updates initially assumed Ci, and the algorithm iteratively computes those Voronoi cells until no further updating of Ci occurs. A parallel procedure corrects the Voronoi cells, iteratively, using a topology matching approach. A reduced touching disc method and a cell-wise computation of the Voronoi diagram allow input in non-general position. Results and performance of the algorithm show robustness and speed of the algorithm in handling a large set of circles.