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

## IDA Technical Reports: abstract

*Generated: Wed, 06 May 2015 07:25:56 *

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
```

*<webmaster@ida.liu.se>*