A RANDOMIZED PARALLEL 3-DIMENSIONAL CONVEX-HULL ALGORITHM FOR COARSE-GRAINED MULTICOMPUTERS

We present a randomized parallel algorithm for constructing the three- dimensional convex hull on a generic p-processor coarse-grained multic omputer with arbitrary interconnection network and n/p local memory pe r processor, where n/p greater than or equal to p(2+epsilon) (for some arbitrarily small epsilon > 0). For any given set of n points in 3-sp ace, the algorithm computes the three-dimensional convex hull, with hi gh probability, in O((nlogn)/p) local computation time and O(1) commun ication phases with at most O(n/p) data sent/received by each processo r. That is, with high probability, the algorithm computes the three-di mensional convex hull of an arbitrary point set in time O((nlogn)/p Gamma(n,p)), where Gamma(n,p) denotes the time complexity of one commu nication phase. The assumption n/p > p(2+epsilon) implies a coarse-gra ined, limited parallelism, model which is applicable to most commercia lly available multiprocessors. In the terminology of the BSP model, ou r algorithm requires, with high probability , O(1) supersteps, synchro nization period L = Theta((nlogn)/p), computation cost O((nlogn)/p), a nd communication cost O((n/p)g).