NC1 parallel 3D convex hull algorithm

Nancy M. Amato, Franco P. Preparata

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we present an O(log n) time parallel algorithm for computing the convex hull of n points in R3. This algorithm uses O(n1+α) 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(log2 n). 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 points 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 divide-and-conquer paradigm.

Original languageEnglish (US)
Title of host publicationProceedings of the 9th Annual Symposium on Computational Geometry
Editors Anon
PublisherPubl by ACM
Pages289-297
Number of pages9
ISBN (Print)0897915828
StatePublished - Dec 1 1993
EventProceedings of the 9th Annual Symposium on Computational Geometry - San Diego, CA, USA
Duration: May 19 1993May 21 1993

Publication series

NameProceedings of the 9th Annual Symposium on Computational Geometry

Conference

ConferenceProceedings of the 9th Annual Symposium on Computational Geometry
CitySan Diego, CA, USA
Period5/19/935/21/93

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'NC<sup>1</sup> parallel 3D convex hull algorithm'. Together they form a unique fingerprint.

Cite this