New sequential and parallel algorithms for computing the \(\beta\)-spectrum

DOI10.1016/j.tcs.2015.03.033zbMath1327.68319OpenAlexW2064648472MaRDI QIDQ2348036

Mirosław Kowaluk, Gabriela Majewska

Publication date: 10 June 2015

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.03.033

zbMATH Keywords

parallel algorithmsneighborhood graphDelaunay triangulation\(\beta\)-skeleton\(\beta\)-spectrum

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• A divide-and-conquer algorithm for constructing relative neighborhood graph
• Parallel computational geometry
• The relative neighbourhood graph of a finite planar set
• Optimal parallel algorithms for point-set and polygon problems
• Time-optimal proximity graph computations on enhanced meshes
• Ray shooting in polygons using geodesic triangulations
• A linear-time construction of the relative neighborhood graph from the Delaunay triangulation
• Beta-skeletons have unbounded dilation
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Ultrafast Expected Time Parallel Algorithms

This page was built for publication: New sequential and parallel algorithms for computing the \(\beta\)-spectrum