Parallel algorithms for higher-dimensional convex hulls

We give fast randomized and deterministic parallel methods for constructing convex hulls in R^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 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(log² 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(nr^{d- 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 R³. This leads to a sequential algorithm for computing the diameter of a point set in R³ with running time O(n log³ n), which is arguably simpler than an algorithm with the same running time by Bronnimann et al.