Carleton University
Technical Report TR-95-14
June 1995
A Randomized Parallel 3D Convex Hull Algorithm for Coarse Grained Multicomputers
Abstract
We present a randomized parallel algorithm for constructing the 3D convex hull on a generic p-processor coarse grained multicomputer with arbitrary interconnection network and n=p local memory per processor, where n / p ≥ p2+e (for some arbitrarily small e > 0). For any given set of n points in 3-space, the algorithm computes the 3D convex hull, with high probability, in O( (n log n) / p ) local computation time and O(1) communication phases with at most O( n / p ) data sent/received by each processor. That is, with high probability, the algorithm computes the 3D convex hull of an arbitrary point set in time O( (n log n) / p + T n,p), where Tn,p denotes the time complexity of one communication phase.In the terminology of the BSP model, our algorithm requires, with high probability, O(1) supersteps and a synchronization period O((n log n) / p ). In the LogP model, the execution time of our algorithm is asymptotically optimal for several architectures.