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

## IDA Technical Reports: abstract

*Generated: Fri, 30 Jan 2015 15:00:17 *

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>*