@techreport{R-89-08,
TITLE = {An Optimal Expected-Time Parallel Algorithm for Voronoi Diagrams},
AUTHOR = {Christos Levcopoulos and Jyrki Katajainen and Andrzej Lingas },
YEAR = {1989},
NUMBER = {R-89-08},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-89-08+abstr},
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.},
IDANR = {LiTH-IDA-R-89-08},
NOTE = {Also in Proc. of the 1st Scandinavian Workshop on Algorithm Theory, Halmstad, Sweden, July 1988}