The Model

We present a randomized parallel algorithm for con-structing the 3D convex hull on a generic p-processor coarse grained multicomputer with arbitrary inter-connection network and n/p local memory per processor, where ~ z p’+ ’ (for some arbitrarily small c> O). For any given set of n points in 3-space, the algorithm computes the 3D convex hull, with high probability, in 0(w) local computation time and 0(1) communication phases with at most 0(~) 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 0(* + I’~,P), where I’~,P denotes the time complexity of one communication phase. In the terminology of the BSP model, our algorithm requires, with high probability, O(1) super-steps and a synchronization period @(%). In the LogP model, the execution time of our algo-rithm is asymptotically optimaJ for several archit ect ures