Distribution-sensitive construction of the greedy spanner

DOI10.1007/s00453-016-0160-9zbMath1360.68867OpenAlexW2155971496WikidataQ59517593 ScholiaQ59517593MaRDI QIDQ527422

Quirijn W. Bouts, Alex P. ten Brink, Sander P. A. Alewijnse, Kevin Buchin

Publication date: 11 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0160-9

zbMATH Keywords

computational geometryspannersgreedy spanneruniform points

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

The Greedy Spanner Is Existentially Optimal

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum dilation stars
• Computing the greedy spanner in linear space
• Region-fault tolerant geometric spanners
• Some dynamic computational geometry problems
• The expected size of some graphs in computational geometry
• Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations
• Probability theory of classical Euclidean optimization problems
• There are planar graphs almost as good as the complete graph
• Computing the greedy spanner in near-quadratic time
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
• Geometric Spanner Networks
• On the expected maximum degree of Gabriel and Yao graphs
• Constructing Delaunay Triangulations along Space-Filling Curves
• Graph spanners
• Approximating the Stretch Factor of Euclidean Graphs
• A Framework for Computing the Greedy Spanner
• Testing Euclidean Spanners