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

DOI10.1016/J.TCS.2023.114054arXiv1212.1095OpenAlexW2886674261MaRDI QIDQ6168083FDOQ6168083

Authors: Daniel Reem 

Publication date: 8 August 2023

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

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.

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

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

zbMATH Keywords

algorithmparallel computingrayvertexVoronoi diagramprojectorwedgeDelaunay graphVoronoi cellcombinatorial representationsubedgesubwedge

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)