Lower bounds on the dilation of plane spanners

DOI10.1007/978-3-319-29221-2_12MaRDI QIDQ5890540zbMATH OpenOpenAlexFDO

Authors Adrian Dumitrescu, Anirban Ghosh

Publication date 23 March 2016

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.07181

zbMATH Keywords

geometric graphstretch factorplane spanner

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05)

Abstract: (I) We exhibit a set of 23 points in the plane that has dilation at least $1.4308$, improving the previously best lower bound of $1.4161$ for the worst-case dilation of plane spanners. (II) For every integer $ngeq13$, there exists an $n$-element point set $S$ such that the degree 3 dilation of $S$ denoted by $delt{a}_0(S,3)extequals1+sqrt3=2.7321ldots$ in the domain of plane geometric spanners. In the same domain, we show that for every integer $ngeq6$, there exists a an $n$-element point set $S$ such that the degree 4 dilation of $S$ denoted by $delt{a}_0(S,4)extequals1+sqrt(5-sqrt5)/2=2.1755ldots$ The previous best lower bound of $1.4161$ holds for any degree. (III) For every integer $ngeq6$, there exists an $n$-element point set $S$ such that the stretch factor of the greedy triangulation of $S$ is at least $2.0268$.

Recommendations

• Lower bounds on the dilation of plane spanners
• Degree four plane spanners: simpler and better
• Degree four plane spanners: simpler and better
• Lattice spanners of low degree
• There are plane spanners of degree 4 and moderate stretch factor

Cites work

• scientific article; zbMATH DE number 4155925 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• A fast algorithm for approximating the detour of a polygonal chain.
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
• Classes of graphs which approximate the complete Euclidean graph
• Computing a minimum-dilation spanning tree is NP-hard
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• Constructing plane spanners of bounded degree and low weight
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• Delaunay graphs are almost as good as complete graphs
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• Generating all triangulations of plane graphs
• Geometric Spanner Networks
• Lattice spanners of low degree
• Lower bounds on the dilation of plane spanners
• Most finite point sets in the plane have dilation \(>1\)
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• On Generalized Diamond Spanners
• On bounded degree plane strong geometric spanners
• On geometric spanners of Euclidean and unit disk graphs
• On plane geometric spanners: a survey and open problems
• On sparse spanners of weighted graphs
• On the geometric dilation of closed curves, graphs, and point sets
• On the stretch factor of Delaunay triangulations of points in convex position
• Plane Spanners of Maximum Degree Six
• Sparse geometric graphs with small dilation
• The geometric dilation of finite point sets
• 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 planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
• There are plane spanners of degree 4 and moderate stretch factor
• Upper Bound on Dilation of Triangulations of Cyclic Polygons

Cited in

(7)

• Lower bounds on the dilation of plane spanners
• Gabriel triangulations and angle-monotone graphs: local routing and recognition
• Lattice spanners of low degree
• scientific article; zbMATH DE number 6868519 (Why is no real title available?)
• Lattice spanners of low degree
• An exact algorithm for the minimum dilation triangulation problem
• On the geometric dilation of closed curves, graphs, and point sets

This page was built for publication: Lower bounds on the dilation of plane spanners

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