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 n/log n) processors in the CRCW PRAM model. The concu rrent write is used only by an integer sorting subroutine. We also obt ain an O(log n)-time and O(n log log n/log n)-processor CRCW PRAM algo rithm for the construction of the medial axis of a convex polygon. Our algorithms use the solution to the duration-unknown task scheduling p roblem due to Cole and Vishkin and the optimal parallel algorithm for the convex hull of a polygon due to Wagener. They are randomized in th e sense that for any given l > 0 they terminate in time O(log n) with probability greater than 1 - n(-1).