Lower Bounds on the Dilation of Plane Spanners

DOI10.1007/978-3-319-29221-2_12zbMATH Open1405.68414arXiv1509.07181OpenAlexW2963798875MaRDI QIDQ5890540FDOQ5890540

Adrian Dumitrescu, Anirban Ghosh

Publication date: 23 March 2016

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

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$.

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)

Cites Work

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

Cited In (4)

• Lattice Spanners of Low Degree
• Title not available (Why is that?)
• Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
• An exact algorithm for the minimum dilation triangulation problem

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)