An NC parallel 3D convex hull algorithm

ABSTRACT

In this paper we present an Ologn time parallel algorithm for computing the convex hull of n points in R³ . This algorithm uses On^1+a processors on a CREW PRAM, for any constant 0 < &dgr; ≤ 1. So far, all adequately documented parallel algorithms proposed for this problem use time at least Olog

2

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 point sets. The contributions of this paper are therefore (i) an Ologn 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.

REFERENCES

• ACGOY88: A. Aggarwal, B. Chazelle, L. Guibas, C. O'Ddnlaing, C. Yap, Parallel Computational Geometry, Algorithmica 3 (198$), pp. 293-327.
• AP92: N. Amato and F. Preparata, The ParaUel 3D Convex Hull Problem Revisited, International Journal of Computational Geometry ~4 Applications 2(2) (1992), pp. 163-174.
• Co88: Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
• CZ90: Richard Cole , Ofer Zajicek, An optimal parallel algorithm for building a data structure for planar point location, Journal of Parallel and Distributed Computing, v.8 n.3, p.280-285, Mar. 1990 [doi>10.1016/0743-7315(90)90103-V]
• C80: Anita Liu Chow, Parallel algorithms for geometric problems, 1980
• DaK89: N. Dadoun , D. G. Kirkpatrick, Parallel construction of subdivision hierarchies, Journal of Computer and System Sciences, v.39 n.2, p.153-165, Oct. 1989 [doi>10.1016/0022-0000(89)90042-1]
• DK90: David P. Dobkin , David G. Kirkpatrick, Determining the separation of preprocessed polyhedra: a unified approach, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.400-413, July 1990, Warwick University, England
• KR91: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• PDW92: W. Preilowski , Elias Dahlhaus , Gerd Wechsung, New Parallel Algorithms for Convex Hull and Triangulation in 3-Dimensional Space, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.442-450, August 24-28, 1992
• PH77: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• PS85: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Verification