Parallelism in Randomized Incremental Algorithms
Guy E. Blelloch, Yan Gu, Julian Shun, Yihan Sun · 2016
In this paper we show that most sequential randomized incremental algorithms are in fact parallel. We consider several random incremental algorithms including algorithms for comparison sorting and Delaunay triangulation; linear programming, closest pair, and smallest enclosing disk in constant dimensions; as well as least-element lists and strongly connected components on graphs.