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^d can be constructed in O(log n) time using O(n log n+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(log n) time using O(n^[d/2] log^c([d2]-[d/2]/) n) work for d⩾4, 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