The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs

DOI10.1016/j.tcs.2023.114054arXiv1212.1095OpenAlexW2886674261MaRDI QIDQ6168083

Daniel Reem

Publication date: 8 August 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

algorithmVoronoi cellparallel computingVoronoi diagramprojectorwedgevertexrayDelaunay graphcombinatorial representationsubedgesubwedge

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new parallel algorithm for constructing Voronoi tessellations from distributed input data
• On the complexity of d-dimensional Voronoi diagrams
• Higher-dimensional Voronoi diagrams in linear expected time
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• A sweepline algorithm for Voronoi diagrams
• Finding the convex hull of a sorted point set in parallel
• Parallel computational geometry
• On parallel computation of Voronoi diagrams
• Parallel construction of subdivision hierarchies
• Design and implementation of a practical parallel Delaunay algorithm
• Voronoi diagrams from convex hulls
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Constructing the Voronoi diagram of a set of line segments in parallel
• A nearly parallel algorithm for the Voronoi diagram of a convex polygon
• Nearest neighbor queries in metric spaces
• Clock construction in fully asynchronous parallel systems and PRAM simulation
• Derandomizing an output-sensitive convex hull algorithm in three dimensions
• Delaunay refinement algorithms for triangular mesh generation
• Fixed points of polarity type operators
• On the computation of zone and double zone diagrams
• A nearly optimal deterministic parallel Voronoi diagram algorithm
• Applications of random sampling in computational geometry. II
• Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane
• Localizing the Delaunay Triangulation and Its Parallel Implementation
• Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• IMPROVEMENTS OF THE INCREMENTAL METHOD FOR THE VORONOI DIAGRAM WITH COMPUTATIONAL COMPARISON OF VARIOUS ALGORITHMS
• A Remark on Stirling's Formula
• PARALLEL DELAUNAY REFINEMENT: ALGORITHMS AND ANALYSES
• Smoothed analysis of algorithms
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Shape from probing
• Optimal Expected-Time Algorithms for Closest Point Problems
• Computing Dirichlet Tessellations in the Plane
• Erratum: Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
• The quickhull algorithm for convex hulls
• Ultrafast Expected Time Parallel Algorithms
• Centroidal Voronoi Tessellations: Applications and Algorithms
• Parallel computation of discrete Voronoi diagrams
• Parallel Delaunay triangulation for particle finite element methods
• Divide-and-conquer for Voronoi diagrams revisited
• Parallelism in random access machines
• Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations
• SCALABLE PARALLEL COMPUTATIONAL GEOMETRY FOR COARSE GRAINED MULTICOMPUTERS
• Quicksort

This page was built for publication: The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs