Parallel algorithms for higher-dimensional convex hulls
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 683-694
- https://doi.org/10.1109/sfcs.1994.365724
Abstract
We give fast randomized and deterministic parallel methods for constructing convex hulls in R/sup d/, 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/sup d/ can be constructed in O(log n) time using O(n log n+n/sup [d/2]/) work, with high probability. We also show that it can be constructed deterministically in O(log/sup 2/ n) time using O(n log n) work for d=3 and in O(log n) time using O(n/sup [d/2]/ log/sup c([d/2]-[d/2]/) n) work for d/spl ges/4, where c>0 is a constant which is optimal for even d/spl ges/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.Keywords
This publication has 49 references indexed in Scilit:
- An efficient algorith for determining the convex hull of a finite planar setPublished by Elsevier ,2002
- On construction of k-wise independent random variablesPublished by Association for Computing Machinery (ACM) ,1994
- Geometric partitioning made easier, even in parallelPublished by Association for Computing Machinery (ACM) ,1993
- Reporting points in halfspacesComputational Geometry, 1992
- Cutting hyperplane arrangementsDiscrete & Computational Geometry, 1991
- Removing randomness in parallel computation without a processor penaltyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- ɛ-nets and simplex range queriesDiscrete & Computational Geometry, 1987
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986
- The Ultimate Planar Convex Hull Algorithm?SIAM Journal on Computing, 1986
- Beweis einer Vermutung von A. VázsonyiActa Mathematica Hungarica, 1956