Parallelism in randomized incremental algorithms

DOI10.1145/3402819MaRDI QIDQ5066936zbMATH OpenOpenAlexFDO

Authors Guy E. Blelloch, Yan Gu, Julian Shun, Yihan Sun

Publication date 31 March 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.05303

zbMATH Keywords

linear programmingDelaunay triangulationclosest pairstrongly connected componentsrandomized incremental algorithmssmallest enclosing diskleast-element lists

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Abstract: In this paper 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 dependences between iterations in an algorithm, and show that the dependence structure is shallow with high probability, or that by violating some dependences the structure is shallow and the work is not increased significantly. We identify three types of algorithms based on their dependences 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 paper shows the first incremental Delaunay triangulation algorithm with optimal work and polylogarithmic depth, which is an open problem for over 30 years. 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-elements lists, and significantly simplify parallel algorithms for several problems.

Recommendations

• Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
• Randomized incremental construction of Delaunay and Voronoi diagrams
• RANDOMIZED PARALLEL ALGORITHMS FOR TRAPEZOIDAL DIAGRAMS
• Optimal randomized parallel algorithms for computational geometry
• scientific article; zbMATH DE number 177830

Cited in

(8)

• On lazy randomized incremental construction
• scientific article; zbMATH DE number 5198953 (Why is no real title available?)
• Pargeo: a library for parallel computational geometry
• scientific article; zbMATH DE number 1419218 (Why is no real title available?)
• Parallelism in random access machines
• From randomizing polynomials to parallel algorithms
• New Scheduling Strategies for Randomized Incremental Algorithms in the Context of Speculative Parallelization
• Multi-core Implementations of Geometric Algorithms

This page was built for publication: Parallelism in randomized incremental algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066936)