A TIME-OPTIMAL PARALLEL ALGORITHM FOR 3-DIMENSIONAL CONVEX HULLS Academic Article

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. 1995 Springer-Verlag New York Inc.

authors

• Amato, Nancy

published proceedings

• ALGORITHMICA

author list (cited authors)

• AMATO, N. M., & PREPARATA, F. P.

citation count

• 3

complete list of authors

• AMATO, NM||PREPARATA, FP

publication date

• August 1995

publisher

• Springer Nature  Publisher

published in

• Algorithmica: an international journal in computer science  Journal

keywords

• 3-dimensional
• Convex Hull
• Deterministic
• Parallel Algorithm
• Pram
• Time-optimal

Digital Object Identifier (DOI)

• 10.1007/BF01293667

start page

• 169

end page

• 182

volume

• 14

issue

• 2

URL

• http://dx.doi.org/10.1007/bf01293667