Constructing the Voronoi diagram of a set of line segments in parallel

DOI10.1007/BF01188708zbMath0766.68134OpenAlexW2036254524MaRDI QIDQ1206435

Michael T. Goodrich, Chee-Keng Yap, Colm P. O'Dunlaing

Publication date: 1 April 1993

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01188708

zbMATH Keywords

Voronoi diagramCREW PRAM

Mathematics Subject Classification ID

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

Related Items (5)

A parallel algorithm for computing Voronoi diagram of a set of circles using touching disc and topology matching ⋮ Finding a closet visible vertex pair between two polygons ⋮ Linear-size nonobtuse triangulation of polygons ⋮ The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs ⋮ A nearly optimal deterministic parallel Voronoi diagram algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding Euler tours in parallel
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• A sweepline algorithm for Voronoi diagrams
• Parallel algorithms for some functions of two convex polygons
• Parallel computational geometry
• A “retraction” method for planning the motion of a disc
• Parallel Merge Sort
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• Parallel Prefix Computation
• Generalization of Voronoi Diagrams in the Plane
• Medial Axis Transformation of a Planar Shape

This page was built for publication: Constructing the Voronoi diagram of a set of line segments in parallel