A randomized parallel algorithm for Voronoi diagrams based on symmetric convex distance functions Original Research Article

This paper presents a randomized parallel algorithm for computing planar Voronoi diagrams of n point sites according to symmetric convex distance functions. This algorithm uses, with high probability, O(n log(n)/p) local computation time and O(n/p) space on the processors plus time for O(1) communication rounds on a coarse grained multicomputer with p processors.