## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 231-241 |

Number of pages | 11 |

Journal | International Journal of Computational Geometry and Applications |

Volume | 6 |

Issue number | 2 |

DOIs | |

State | Published - Jan 1 1996 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Computational Theory and Mathematics
- Computational Mathematics
- Applied Mathematics

## Keywords

- Computational geometry
- Convex hull
- PRAM
- Parallel algorithms