A nearly optimal deterministic parallel Voronoi diagram algorithm

DOI10.1007/BF01944352MaRDI QIDQ1817002zbMATH OpenOpenAlexFDO

Authors Michael T. Goodrich, Richard 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)

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3785798 (Why is no real title available?)
• scientific article; zbMATH DE number 177831 (Why is no real title available?)
• scientific article; zbMATH DE number 3544865 (Why is no real title available?)
• A new duality result concerning Voronoi diagrams
• A sweepline algorithm for Voronoi diagrams
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• Constructing the Voronoi diagram of a set of line segments in parallel
• Dynamic computational geometry on meshes and hypercubes
• Improved deterministic parallel integer sorting
• On parallel computation of Voronoi diagrams
• On the time required to sum n semigroup elements on a parallel machine with simultaneous writes
• Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
• Parallel Prefix Computation
• Parallel algorithms for some functions of two convex polygons
• Parallel computational geometry
• Parallelism in Comparison Problems
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Searching, Merging, and Sorting in Parallel Computation
• Some dynamic computational geometry problems

Cited in

(7)

• Optimal computation of the Voronoi diagram of disjoint clusters
• On parallel computation of Voronoi diagrams
• An improved parallel algorithm for constructing Voronoi diagram on a mesh-connected computer
• The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs
• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• An extension to \textsc{Voro++} for multithreaded computation of Voronoi cells
• A new parallel algorithm for constructing Voronoi tessellations from distributed input data

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

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