Optimal Parallel Randomized Algorithms for 3-D Convex Hulls and Related Problems

We present further applications of random sampling techniques which have been used for deriving efficient parallel algorithms by Reif and Sen [27]. In this paper we present an optimal parallel randomized algorithm for computing intersection of half-spaces in three dimensions. Because of well-known reductions, our methods also yield equally efficient algorithms for fundamental problems like the convex hull in three dimensions, Voronoi diagram of point sites on a plane and Euclidean minimal spanning tree. Our algorithms run in time T = O(log n) for worst-case inputs and uses P = O(n) processors in a CREW PRAM model where n is the input size. They are randomized in the sense that they use a total of only O(log² n) random bits and terminate in the claimed time bound with probability 1 - n for any fixed > 0. They are also optimal in P T product since the sequential time bound for all these problems is n log n). The best known deterministic parallel algorithms for 2-D Voronoi-..