Parallel algorithms for higher-dimensional convex hulls

Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos

Research output: Contribution to journalConference articlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)683-694
Number of pages12
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs
StatePublished - 1994
Externally publishedYes
EventProceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science - Santa Fe, NM, USA
Duration: Nov 20 1994Nov 22 1994

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'Parallel algorithms for higher-dimensional convex hulls'. Together they form a unique fingerprint.

Cite this