A fast parallel algorithm for finding the convex hull of a sorted point set

Omer Berkman, Baruch Schieber, Uzi Vishkin

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

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 languageEnglish (US)
Pages (from-to)231-241
Number of pages11
JournalInternational Journal of Computational Geometry and Applications
Volume6
Issue number2
DOIs
StatePublished - 1996
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'A fast parallel algorithm for finding the convex hull of a sorted point set'. Together they form a unique fingerprint.

Cite this