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 pro cessor, where n/p >= p~(2+#epsilon#) (for some arbitrarily small #epsilon# > 0). For any given set of n points in 3-space, the algorithm computes the 3D convex hull, with high probability, in O( nlogn / 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( nlogn / p + #GAMMA# _(n,p)), where #GAMMA# _(n,p) denotes the time complexity of one communication phase.
展开▼
