A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon

We present a parallel algorithm for the Voronoi diagram of the set of vertices of a convex polygon. The algorithm runs in time O(log n) and uses O(n log log nlog n) processors in the CRCW PRAM model. The concurrent write is used only by an integer sorting subroutine. We also obtain an O(log n)-time and O(n log log nlog n)-processor CRCW PRAM algorithm for the construction of the medial axis of a convex polygon. Our algorithms use the solution to the duration-unknown task scheduling problem due to Cole and Vishkin and the optimal parallel algorithm for the convex hull of a polygon due to Wagener. They are randomized in the sense that for any given l > 0 they terminate in time O(log n) with probability greater than 1 − n−1.