ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract. We present a randomized parallel algorithm for constructing the three-dimensional convex hull on a generic p-processor coarse-grained multicomputer with arbitrary interconnection network and n/p local memory per processor, where n/p ≥ p 2+ε (for some arbitrarily small ε 〉 0). For any given set of n points in 3-space, the algorithm computes the three-dimensional 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 three-dimensional convex hull of an arbitrary point set in time $O((n\log n)/{p} + \Gamma_{n,p})$ , where Γ n,p denotes the time complexity of one communication phase. The assumption n/p ≥ p 2+ε implies a coarse-grained, limited parallelism, model which is applicable to most commercially available multiprocessors. In the terminology of the BSP model, our algorithm requires, with high probability, O(1) supersteps, synchronization period $L = \Theta((n\log n)/{p})$ , computation cost $O((n\log n)/{p})$ , and communication cost O((n/p) g).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s002240000067
Permalink
