A nearly parallel algorithm for the Voronoi diagram of a convex polygon

DOI10.1016/S0304-3975(96)00024-2zbMath0902.68202OpenAlexW2067187253MaRDI QIDQ1269914

Piotr Berman, Andrzej Lingas

Publication date: 22 October 1998

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00024-2

zbMATH Keywords

Voronoi diagramCRCW PRAM model

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal parallel algorithms for point-set and polygon problems
• New applications of random sampling in computational geometry
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• RANDOMIZATION YIELDS SIMPLE O(n log^⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
• Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
• ON COMPUTING VORONOI DIAGRAMS FOR SORTED POINT SETS
• A LINEAR-TIME RANDOMIZED ALGORITHM FOR THE BOUNDED VORONOI DIAGRAM OF A SIMPLE POLYGON
• A new duality result concerning Voronoi diagrams

This page was built for publication: A nearly parallel algorithm for the Voronoi diagram of a convex polygon