Polling: a new randomized sampling technique for computational geometry

Abstract

We introduce a new randomized sampling technique, called Polling which has applications to deriving efficient parallel algorithms. As an example of its use in computational geometry, we present an optimal parallel randomized algorithm for intersection of half-spaces in three dimensions. Because of well-known reductions, our methods also yield equally efficient algorithms for fundamental problems like t,he 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(logn) 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(log2 n) random bits and terminate in the claimed time bound with probability 1- n--(y for any o> 0. They are also optimal in P. T product since the sequential time bound for all these problems is Sl(nlogn). The best known deterministic parallel algorithms for 2-D Voronoi-diagram and 3-D Convex hull run in O(log2 n) and O(log2 nlog * n) time respectively while using O(n) processors.