New sequential and parallel algorithms for computing the -spectrum

DOI10.1016/J.TCS.2015.03.033MaRDI QIDQ2348036zbMATH OpenOpenAlexFDO

Authors 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

\(\beta\)-skeleton\(\beta\)-spectrumDelaunay triangulationneighborhood graphparallel algorithms

Mathematics Subject Classification ID

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

Recommendations

• New sequential and parallel algorithms for computing the -spectrum
• Fast algorithms for computing -skeletons and their relatives.
• Output-sensitive algorithm for computing -skeletons
• -skeletons for a set of line segments in R^2
• Optimal and suboptimal robust algorithms for proximity graphs

Cites work

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

Cited in

(4)

• Output-sensitive algorithm for computing -skeletons
• New sequential and parallel algorithms for computing the -spectrum
• -skeletons for a set of line segments in R^2
• Fast algorithms for computing -skeletons and their relatives.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2348036)