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

IDA Technical Reports: abstract

Generated: Thu, 24 Apr 2014 08:42:46

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>