Shashanka Ubaru, Lior Horesh, et al.
Journal of Biomedical Informatics
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.
Shashanka Ubaru, Lior Horesh, et al.
Journal of Biomedical Informatics
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering