About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
International Journal of Computational Geometry and Applications
Paper
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.