NC1 parallel 3D convex hull algorithm

Nancy M. Amato; Franco P. Preparata

NC¹ parallel 3D convex hull algorithm

Nancy M. Amato, Franco P. Preparata

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In this paper we present an O(log n) time parallel algorithm for computing the convex hull of n points in R³. This algorithm uses O(n^1+α) 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(log² 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 language	English (US)
Title of host publication	Proceedings of the 9th Annual Symposium on Computational Geometry
Editors	Anon
Publisher	Publ by ACM
Pages	289-297
Number of pages	9
ISBN (Print)	0897915828
State	Published - Dec 1 1993
Event	Proceedings of the 9th Annual Symposium on Computational Geometry - San Diego, CA, USA Duration: May 19 1993 → May 21 1993

Publication series

Name	Proceedings of the 9th Annual Symposium on Computational Geometry

Conference

Conference	Proceedings of the 9th Annual Symposium on Computational Geometry
City	San Diego, CA, USA
Period	5/19/93 → 5/21/93

ASJC Scopus subject areas

Engineering(all)

Access to Document

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

Cite this

@inproceedings{94759d90b51745d08b95c29c752adfb6,

title = "NC1 parallel 3D convex hull algorithm",

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.",

author = "Amato, {Nancy M.} and Preparata, {Franco P.}",

year = "1993",

month = dec,

day = "1",

language = "English (US)",

isbn = "0897915828",

series = "Proceedings of the 9th Annual Symposium on Computational Geometry",

publisher = "Publ by ACM",

pages = "289--297",

editor = "Anon",

booktitle = "Proceedings of the 9th Annual Symposium on Computational Geometry",

note = "Proceedings of the 9th Annual Symposium on Computational Geometry ; Conference date: 19-05-1993 Through 21-05-1993",

}

TY - GEN

T1 - NC1 parallel 3D convex hull algorithm

AU - Amato, Nancy M.

AU - Preparata, Franco P.

PY - 1993/12/1

Y1 - 1993/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027837127&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027837127&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027837127

SN - 0897915828

T3 - Proceedings of the 9th Annual Symposium on Computational Geometry

SP - 289

EP - 297

BT - Proceedings of the 9th Annual Symposium on Computational Geometry

A2 - Anon, null

PB - Publ by ACM

T2 - Proceedings of the 9th Annual Symposium on Computational Geometry

Y2 - 19 May 1993 through 21 May 1993

ER -