A nearly optimal deterministic parallel Voronoi diagram algorithm

DOI10.1007/BF01944352zbMath0860.68106OpenAlexW2099646511MaRDI QIDQ1817002

Michael T. Goodrich, Richard John Cole, Colm P. O'Dunlaing

Publication date: 29 January 1997

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01944352

zbMATH Keywords

Voronoi diagramCRCW algorithm

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed algorithms (68W15)

Related Items (2)

The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs ⋮ A new parallel algorithm for constructing Voronoi tessellations from distributed input data

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dynamic computational geometry on meshes and hypercubes
• Some dynamic computational geometry problems
• On the time required to sum n semigroup elements on a parallel machine with simultaneous writes
• A sweepline algorithm for Voronoi diagrams
• Parallel algorithms for some functions of two convex polygons
• Parallel computational geometry
• On parallel computation of Voronoi diagrams
• Improved deterministic parallel integer sorting
• Constructing the Voronoi diagram of a set of line segments in parallel
• Searching, Merging, and Sorting in Parallel Computation
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• Parallel Prefix Computation
• Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
• Parallelism in Comparison Problems
• A new duality result concerning Voronoi diagrams

This page was built for publication: A nearly optimal deterministic parallel Voronoi diagram algorithm