Fjällström, P.-O., Katajainen, J., Levcopoulos, C., and Petersson, O. (1989). A Sublogarithmic Parallel Algorithm for Finding the Convex Hull of Sorted Points. Technical Report LiTH-IDA-R-89-29, Department of Computer and Information Science, Linköping University, Sweden. Also in BIT 30(1990), 378-384. (bibtex),
Abstract: We present a parallel algorithm for finding the convex hull of a sorted set of points in the plane. Our algorithm runs in O(log n/log log n) time using O(n log log n/log n) processors in the CRCW PRAM computational model, which is time and cost optimal. Our algorithm is based on cube root of n divide-and-conquer. Furthermore, we use a simple, pointer-based data structure.
CS Dept TR Overview