Bounded-degree plane geometric spanners in practice

DOI10.1145/3582497MaRDI QIDQ6579765zbMATH OpenFDO

Authors Frederick Anderson, Anirban Ghosh, Matthew Graham, Lucas Mougeot, David Wisnosky

Publication date 26 July 2024

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3582497

zbMATH Keywords

geometric graphplane spannerstretch-factor

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• Approximating the average stretch factor of geometric graphs
• Approximating the Stretch Factor of Euclidean Graphs
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• Computing the maximum detour of a plane geometric graph in subquadratic time
• Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
• CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
• Constructing plane spanners of bounded degree and low weight
• Degree four plane spanners: simpler and better
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• Experimental study of geometric \(t\)-spanners
• Experiments with unit disk cover algorithms for covering massive pointsets
• Fast Algorithms for Geometric Traveling Salesman Problems
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Geometric minimum spanning trees via well-separated pair decompositions
• Geometric Spanner Networks
• scientific article; zbMATH DE number 6776481 (Why is no real title available?)
• Improved local algorithms for spanner construction
• Lattice spanners of low degree
• Lower bounds on the dilation of plane spanners
• Most finite point sets in the plane have dilation \(>1\)
• On bounded degree plane strong geometric spanners
• On plane geometric spanners: a survey and open problems
• On spanners and lightweight spanners of geometric graphs
• Planar Hop Spanners for Unit Disk Graphs
• Plane hop spanners for unit disk graphs: simpler and better
• Plane Spanners of Maximum Degree Six
• Practical and efficient algorithms for the geometric hitting set problem
• Sparse hop spanners for unit disk graphs
• The stretch factor of \(L _{1}\)- and \(L _{ \infty }\)-Delaunay triangulations
• The stretch factor of the Delaunay triangulation is less than 1.998
• There are planar graphs almost as good as the complete graph
• There are plane spanners of degree 4 and moderate stretch factor
• Towards plane spanners of degree 3

Cited in

(1)

• Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average degrees

This page was built for publication: Bounded-degree plane geometric spanners in practice

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