Parallel Algorithms for Higher-Dimensional Convex Hulls

We give fast randomized and deterministic parallel methods for constructing convex hulls in R/sup d/, for any fixed d. Our methods are for the weakest shared-memory model, the EREW PRAM, and have optimal work bounds (with high probability for the randomized methods). In particular, we show that the convex hull of n points in R/sup d/ can be constructed in O(log n) time using O(n log n+n/sup [d/2]/) work, with high probability. We also show that it can be constructed deterministically in O(log/sup 2/ n) time using O(n log n) work for d=3 and in O(log n) time using O(n/sup [d/2]/ log/sup c([d/2]-[d/2]/) n) work for d/spl ges/4, where c>0 is a constant which is optimal for even d/spl ges/4. We also show how to make our 3-dimensional methods output-sensitive with only a small increase in running time. These methods can be applied to other problems as well. >

Authors

• Nancy M. Amato
• Michael T. Goodrich
• Edgar A. Ramos

Keywords

• Parallel algorithms
• Phase change random access memory
• Data structures
• Geometry
• Radio access networks
• Size measurement
• High-dimensional
• Convex Hull
• Parallel Algorithm
• High Probability
• Running Time
• Random Method
• Local Point
• Sequential Algorithm
• Ball Of Radius
• Deterministic Methods
• Solid Spheres
• Total Size
• Simplex
• Parallelization
• Working Model
• Total Work
• Voronoi Diagram
• Recursive Algorithm
• Algorithm Running
• N Log N
• Hierarchical Decomposition
• Delaunay Triangulation