IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Sat, 26 Jul 2014 13:11:46

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.

Goto (at Linköping University): CS Dept TR Overview