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

DOI10.1016/J.TCS.2023.114054MaRDI QIDQ6168083zbMATH OpenOpenAlexFDO

Authors 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

algorithmparallel computingrayvertexVoronoi diagramprojectorwedgeDelaunay graphVoronoi cellcombinatorial representationsubedgesubwedge

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: The Voronoi diagram is a certain geometric data structure which has numerous applications in various scientific and technological fields. The theory of algorithms for computing 2D Euclidean Voronoi diagrams of point sites is rich and useful, with several different and important algorithms. However, this theory has been quite steady during the last few decades in the sense that no essentially new algorithms have entered the game. In addition, most of the known algorithms are serial in nature and hence cast inherent difficulties on the possibility to compute the diagram in parallel. In this paper we present the projector algorithm: a new and simple algorithm which enables the (combinatorial) computation of 2D Voronoi diagrams. The algorithm is significantly different from previous ones and some of the involved concepts in it are in the spirit of linear programming and optics. Parallel implementation is naturally supported since each Voronoi cell can be computed independently of the other cells. A new combinatorial structure for representing the cells (and any convex polytope) is described along the way and the computation of the induced Delaunay graph is obtained almost automatically.

Recommendations

• A nearly optimal deterministic parallel Voronoi diagram algorithm
• A parallel algorithm for constructing projection polyhedra
• On parallel computation of Voronoi diagrams
• A nearly parallel algorithm for the Voronoi diagram of a convex polygon
• Parallel computation of discrete Voronoi diagrams (extended abstract)
• scientific article; zbMATH DE number 4062598
• A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon
• An improved parallel algorithm for constructing Voronoi diagram on a mesh-connected computer
• Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane
• A new parallel algorithm for constructing Voronoi tessellations from distributed input data

Cites work

• scientific article; zbMATH DE number 3987367 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 4062598 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 108004 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 1224949 (Why is no real title available?)
• scientific article; zbMATH DE number 589497 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1455125 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• scientific article; zbMATH DE number 1424292 (Why is no real title available?)
• scientific article; zbMATH DE number 3320765 (Why is no real title available?)
• scientific article; zbMATH DE number 3059214 (Why is no real title available?)
• scientific article; zbMATH DE number 3069632 (Why is no real title available?)
• A Remark on Stirling's Formula
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• A nearly optimal deterministic parallel Voronoi diagram algorithm
• A nearly parallel algorithm for the Voronoi diagram of a convex polygon
• A new parallel algorithm for constructing Voronoi tessellations from distributed input data
• A sweepline algorithm for Voronoi diagrams
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Applications of random sampling in computational geometry. II
• Centroidal Voronoi Tessellations: Applications and Algorithms
• Clock construction in fully asynchronous parallel systems and PRAM simulation
• Computing Dirichlet Tessellations in the Plane
• Constructing the Voronoi diagram of a set of line segments in parallel
• Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in space
• Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations
• Delaunay refinement algorithms for triangular mesh generation
• Derandomizing an output-sensitive convex hull algorithm in three dimensions
• Design and implementation of a practical parallel Delaunay algorithm
• Divide-and-conquer for Voronoi diagrams revisited
• Erratum: Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
• Finding the convex hull of a sorted point set in parallel
• Fixed points of polarity type operators
• Higher-dimensional Voronoi diagrams in linear expected time
• IMPROVEMENTS OF THE INCREMENTAL METHOD FOR THE VORONOI DIAGRAM WITH COMPUTATIONAL COMPARISON OF VARIOUS ALGORITHMS
• Introduction to algorithms
• Localizing the Delaunay triangulation and its parallel implementation
• Nearest neighbor queries in metric spaces
• On parallel computation of Voronoi diagrams
• On the complexity of d-dimensional Voronoi diagrams
• On the computation of zone and double zone diagrams
• Optimal Expected-Time Algorithms for Closest Point Problems
• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane
• PARALLEL DELAUNAY REFINEMENT: ALGORITHMS AND ANALYSES
• Parallel Delaunay triangulation for particle finite element methods
• Parallel computation of discrete Voronoi diagrams (extended abstract)
• Parallel computational geometry
• Parallel construction of subdivision hierarchies
• Parallelism in random access machines
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Quicksort
• Randomized incremental construction of Delaunay and Voronoi diagrams
• SCALABLE PARALLEL COMPUTATIONAL GEOMETRY FOR COARSE GRAINED MULTICOMPUTERS
• Shape from probing
• Smoothed analysis of algorithms
• Stochastic geometry and its applications
• The quickhull algorithm for convex hulls
• Ultrafast Expected Time Parallel Algorithms
• Voronoi diagrams from convex hulls

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

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