Parallelism in Randomized Incremental Algorithms
- 19 September 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 67 (5), 1-27
- https://doi.org/10.1145/3402819
Abstract
In this article, we show that many sequential randomized incremental algorithms are in fact parallel. We consider algorithms for several problems, including Delaunay triangulation, linear programming, closest pair, smallest enclosing disk, least-element lists, and strongly connected components. We analyze the dependencies between iterations in an algorithm and show that the dependence structure is shallow with high probability or that, by violating some dependencies, the structure is shallow and the work is not increased significantly. We identify three types of algorithms based on their dependencies and present a framework for analyzing each type. Using the framework gives work-efficient polylogarithmic-depth parallel algorithms for most of the problems that we study. This article shows the first incremental Delaunay triangulation algorithm with optimal work and polylogarithmic depth. This result is important, since most implementations of parallel Delaunay triangulation use the incremental approach. Our results also improve bounds on strongly connected components and least-element lists and significantly simplify parallel algorithms for several problems.Keywords
Funding Information
- NSF (CCF-1314590 and CCF-1533858)
- Miller Institute for Basic Research in Science at UC Berkeley
- Intel Science and Technology Center for Cloud Computing
This publication has 56 references indexed in Scilit:
- Efficient distributed approximation algorithms via probabilistic tree embeddingsDistributed Computing, 2012
- A tight bound on approximating arbitrary metrics by tree metricsJournal of Computer and System Sciences, 2004
- Two-variable linear programming in parallelComputational Geometry, 2002
- A Randomized Parallel Algorithm for Single-Source Shortest PathsJournal of Algorithms, 1997
- Time-work tradeoffs for parallel algorithmsJournal of the ACM, 1997
- A nearly optimal deterministic parallel Voronoi diagram algorithmAlgorithmica, 1996
- Incremental topological flipping works for regular triangulationsAlgorithmica, 1996
- Parallel linear programming in fixed dimension almost surely in constant timeJournal of the ACM, 1994
- Randomized incremental construction of Delaunay and Voronoi diagramsAlgorithmica, 1992
- An optimal parallel algorithm for linear programming in the planeInformation Processing Letters, 1990