We present an \(O(\log^ 3n)\) algorithm for constructing the Voronoi diagrams of a set of n points on a shared memory parallel computer, where concurrent reads are allowed but no two processors can simultaneously attempts to write into the same memory location. If concurrent writes are allowed, the algorithm would run in \(O(\log^ 2n)\) time.
Recommendations
- Parallel computation of discrete Voronoi diagrams (extended abstract)
- A nearly optimal deterministic parallel Voronoi diagram algorithm
- 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
- A nearly parallel algorithm for the Voronoi diagram of a convex polygon
- A new parallel algorithm for constructing Voronoi tessellations from distributed input data
- Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane
- Parallel Voronoi diagram in \(L_ 1(L_{\infty})\) metric on a mesh- connected computer
- An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram
Cited in
(25)- An improved parallel algorithm for constructing Voronoi diagram on a mesh-connected computer
- Constructing the Voronoi diagram of a set of line segments in parallel
- A nearly parallel algorithm for the Voronoi diagram of a convex polygon
- Some results on the computation of Voronoi diagrams on a mesh with multiple broadcasting.
- A nearly optimal deterministic parallel Voronoi diagram algorithm
- Voronoi-like partition of lattice in cellular automata
- Computing the topology of Voronoï diagrams of parallel half-lines
- An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram
- scientific article; zbMATH DE number 4155940 (Why is no real title available?)
- scientific article; zbMATH DE number 4062598 (Why is no real title available?)
- scientific article; zbMATH DE number 140455 (Why is no real title available?)
- scientific article; zbMATH DE number 177538 (Why is no real title available?)
- scientific article; zbMATH DE number 177831 (Why is no real title available?)
- scientific article; zbMATH DE number 1255658 (Why is no real title available?)
- Calculating Voronoi diagrams using simple chemical reactions
- ON COMPUTING VORONOI DIAGRAMS FOR SORTED POINT SETS
- scientific article; zbMATH DE number 934894 (Why is no real title available?)
- A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon
- Parallel computation of discrete Voronoi diagrams (extended abstract)
- A new parallel algorithm for constructing Voronoi tessellations from distributed input data
- A randomized parallel algorithm for Voronoi diagrams based on symmetric convex distance functions
- An extension to \textsc{Voro++} for multithreaded computation of Voronoi cells
- The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs
- A time-optimal parallel algorithm for the computing of Voronoi-diagrams
- Parallel Voronoi diagram in \(L_ 1(L_{\infty})\) metric on a mesh- connected computer
This page was built for publication: On parallel computation of Voronoi diagrams
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1123595)
