TY - JOUR

T1 - Parallel algorithms for higher-dimensional convex hulls

AU - Amato, Nancy M.

AU - Goodrich, Michael T.

AU - Ramos, Edgar A.

N1 - Funding Information:
This research supported in part by an AT&T Bell Laboratories Graduate Fellowship and by NSF Grant CCR-9315696. This research supported by the NSF under Grants IRI-9116843 and CCR-9300079. A portion of this effort was done while this author was visiting the University of Illinois at Urbana-Charnpaign. This research supported in part by NSF Grant CCR-9118874. We would like to thank Ken Clarkson, Herbert Edelsbrunner, Yossi Matias, Jiff Matousek, Franco Preparata, and Jack Snoeyink for helpful comments concerning the topics of this paper.
Funding Information:
* Ths research supported in part by an AT&T Bell Laboratones Graduate Fellowshp and by NSF Grant CCR-9315696 tThis research supported by the NSF under Grants IRI-9116843 and CCR-9300079 A portion of this effort was done whle this author was visiting the University of Illinois at Urbana-Champrugn $This research supported in part by NSF Grant CCR-9118874
Publisher Copyright:
© 1994 IEEE

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0002530128&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0002530128&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1994.365724

DO - 10.1109/SFCS.1994.365724

M3 - Conference article

AN - SCOPUS:0002530128

SN - 0272-5428

SP - 683

EP - 694

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

T2 - Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science

Y2 - 20 November 1994 through 22 November 1994

ER -