Levcopoulos, C., Katajainen, J., and Lingas, A. (1989). An Optimal Expected-Time Parallel Algorithm for Voronoi Diagrams. Technical Report LiTH-IDA-R-89-08, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of the 1st Scandinavian Workshop on Algorithm Theory, Halmstad, Sweden, July 1988. (bibtex),
Abstract: We present a parallel algorithm which constructs the Voronoi diagram of a planar n-point set within a square window. When the points are independently drawn from a uniform distribution, the algorithm runs in O(log n) expected time on CRCW PRAM with O(n log n) processors. The fast operation of the algorithm results from the efficiency of a new multi-level bucketing technique convenient in processor assignment. The concurrent write is used only for the distribution of points in their home buckets in the bottom level.
CS Dept TR Overview