A fast parallel algorithm for finding the convex hull of a sorted point set

Abstract

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 Ω(log 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 time-processor product of the algorithm, which is linear, cannot be unproved, and (2) the running time, which is doubly logarithmic, cannot be unproved even by using a linear number of processors. The algorithm demonstrates the power of the "the divide-and-conquer doubly logarithmicparadigm" by presenting a non-trivial extension to situations that previously were known to have only slower algorithms.