Fast Parallel Algorithms for Voronoi Diagrams
M.T. Goodrich, Colm Ó'Dúnlaing, Chee Keng Yap · Purdue e-Pubs (Purdue University System) · 1985
We present two parallel algorithms for constructing the Voronoi diagram of a. aet of n > 0 line segments in the plane:a) The first algorithm runs in 000g2 n) time using O(n) processors.This improves the previous best results (by A. Chow and also by Aggarwal, Chazelle, Guibas, 6'Dunlaing and Yap) in two respects.First we improve the running time by a factor of O(logn) and second the original results allow only aets ofpointa.b) By using O(n1+() processors.for any f.> 0, we improve the running time to 00ogn).This is the fastest known algorithm uaing a subquadratic number of processors.The results combine a number of techniques: a new O(logn) method for point location in certain tree-shaped Voronoi diagrams, a method of Aggarwal et al for reducing contour tracing to merging tree-shaped Voronoi diagrams, and a technique of Yap for computing the Voronoi diagrams of line segments.The computational model we use is the CREW PRAM (Concurrent-Read, Exclusive-Write Parallel RAM).