A Fast Parallel Algorithm For Finding The Convex Hull Of A Sorted Point Set

We present a parallel algorithm for finding the convex hull of a sorted point set. The algorithm runs in O(log log n) (doubly logarithmic) time using n= log log n processors on a Common CRCW PRAM. To break the\Omega\Gammae/2 n= log log n) time barrier required to output the convex hull in a contiguous array, we introduce a novel data structure for representing the convex hull. The algorithm is optimal in two respects: (1) the timeprocessor product of the algorithm, which is linear, cannot be improved, and (2) the running time, which is doubly logarithmic, cannot be improved even by using a linear number of processors. The algorithm demonstrates the power of the "the divide--and-- conquer doubly logarithmic paradigm" by presenting a non-trivial extension to situations that previously were known to have only slower algorithms. Keywords: Parallel algorithms, computational geometry, convex hull, PRAM. 1. Introduction We consider the following problem: given n points in the plane in a so..