A time-optimal parallel algorithm for three-dimensional convex hulls

N. M. Amato, F. P. Preparata

Research output: Contribution to journalArticle

Abstract

In this paper we present an O(1/α log n)-time parallel algorithm for computing the convex hull of n points in ℜ3. This algorithm uses O(@#@ n1+a) processors on a CREW PRAM, for any constant 0 < α ≤1. So far, all adequately documented parallel algorithms proposed for this problem use time at least O(log2n). In addition, the algorithm presented here is the first parallel algorithm for the three-dimensional convex hull problem that is not based on the serial divide-and-conquer algorithm of Preparata and Hong, whose crucial operation is the merging of the convex hulls of two linearly separated point sets. The contributions of this paper are therefore (i) an O(log n)-time parallel algorithm for the three-dimensional convex hull problem, and (ii) a parallel algorithm for this problem that does not follow the traditional paradigm.

Original languageEnglish (US)
Pages (from-to)169-182
Number of pages14
JournalAlgorithmica
Volume14
Issue number2
DOIs
StatePublished - Aug 1 1995
Externally publishedYes

Keywords

  • Convex hull
  • Deterministic
  • PRAM
  • Parallel algorithm
  • Three-dimensional
  • Time-optimal

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A time-optimal parallel algorithm for three-dimensional convex hulls'. Together they form a unique fingerprint.

  • Cite this