Answers are grounded in this paper and cite their sources.
The randomized incremental convex hull algorithm is one of the most practical and important geometric algorithms in the literature. Due to its simplicity, and the fact that many points or facets can be added independently, it is also widely used in parallel convex hull implementations. However, to date there have been no non-trivial theoretical bounds on the parallelism available in these implementations. In this paper, we provide a strong theoretical analysis showing that the standard incremental algorithm is inherently parallel. In particular, we show that for n points in any constant dimension, the algorithm has O(log n) dependence depth with high probability. This leads to a simple work-optimal parallel algorithm with polylogarithmic span with high probability.
No takes yet. Share an insight, caveat, or question.
Blelloch et al. (2020) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: