IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Tue, 30 Sep 2014 15:51:29

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.


Goto (at Linköping University): CS Dept TR Overview
<webmaster@ida.liu.se>