We give fast randomized and deterministic parallel methods for constructing convex hulls in Rd, for any fixed d. Our methods are for the weakest shared-memory model, the EREW PRAM, and have optimal work bounds (with high probability for the randomized methods). In particular, we show that the convex hull of n points in R can be constructed in O(logn) time using O(nlogn + n[d/2]) work, with high probability. We also show that it can be constructed deterministically in O(log2 n) time using O(n log n) work for d = 3 and in O(logn) time using (equation presented) where c> 0 is a constant, which is optimal for even d > 4. We also show how to make our 3-dimensional methods output-sensitive with only a small increase in running time. These methods can be applied to other problems as well. A variation of the convex hull algorithm for even dimensions deterministically constructs a (1/r)-cutting of n hyperplanes in R.d in O(logn) time using optimal O(nrd- 1) work; when r = n, we obtain their arrangement and a point location data structure for it. With appropriate modifications, our deterministic 3-dimensional convex hull algorithm can be used to compute, in the same resource bounds, the intersection of n balls of equal radius in R3. This leads to a sequential algorithm for computing the diameter of a point set in R3 with running time O(n log3 n), which is arguably simpler than an algorithm with the same running time by Bronnimann et al.
|Number of pages
|Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
|Published - 1994
|Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science - Santa Fe, NM, USA
Duration: Nov 20 1994 → Nov 22 1994
ASJC Scopus subject areas
- General Computer Science