A randomized algorithm for the Voronoi diagram of line segments on coarse-grained multiprocessors
We present a randomized algorithm for computing the Voronoi diagram of line segments using coarse-grained parallel machines. Operating on P processors, for any input of n line segments, this algorithm performs O((n log n)/P) local operations per processor, O(n/P) messages per processor, and O(1) communication phases, with high probability for n = Omega (P3+epsilon).
voronoi diagram coarse-grained parallel algorithms computational geometry