A nearly optimal deterministic parallel Voronoi diagram algorithm

This paper improves upon the result described in the 1990 ICALP paper. It describes an n-processor, O(loglog(n)) time parallel algorithm which constructs the Voronoi deagram of a set of n points in the plane. The model of computation is a CRCW (concurrent-read, concurrent write) PRAM (parallel random-access machine), capable of exact integer arichmetoc in constant time.

This paper amplifies and improves upon the 1990 conference paper `Merging free trees in parallel...'. As previously, the approach uses divide-and-conquer, exploiting so-called `beachlines' (called `proximity envelopes' in the conference paper). In the conference paper the beachlines were precomputed using nlog(n) processors (CREW --- exclusive write). The same effect is produced in this paper by precomputing approximations to the beachlines using n processors (CRCW). Thus we use a more powerful model of computation to help reduce the processor requirement to n. The paper remarks that our methods cannot be adapted to exclusive-write machines in the same run-times.