Lattice spanners of low degree

DOI10.1007/978-3-319-29221-2_13MaRDI QIDQ2795942zbMATH 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/1602.04381

zbMATH Keywords

geometric graphplanar latticestretch factorplane spannervertex dilation

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: Let $delt{a}_0(P,k)$ denote the degree $k$ dilation of a point set $P$ in the domain of plane geometric spanners. If $Lambda$ is the infinite square lattice, it is shown that $1+sqrt2leqdelt{a}_0(Lambda,3)leq(3+2sqrt2),5^{-1/2}=2.6065ldots$ and $delt{a}_0(Lambda,4)=sqrt2$. If $Lambda$ is the infinite hexagonal lattice, it is shown that $delt{a}_0(Lambda,3)=1+sqrt3$ and $delt{a}_0(Lambda,4)=2$. All our constructions are planar lattice tilings constrained to degree $3$ or $4$.

Recommendations

• Lattice spanners of low degree
• Lower bounds on the dilation of plane spanners
• Lower bounds on the dilation of plane spanners
• Towards plane spanners of degree 3
• Towards plane spanners of degree 3

Cites work

• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• A fast algorithm for approximating the detour of a polygonal chain.
• 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
• Degree-constrained spanners for multidimensional grids
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• Geometric Spanner Networks
• Grid spanners
• 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 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
• 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

Cited in

(6)

• Lower bounds on the dilation of plane spanners
• Bounded-degree plane geometric spanners in practice
• A note on optimal degree-three spanners of the square lattice
• Generating Low-Degree 2-Spanners
• Lattice spanners of low degree
• Lower bounds on the dilation of plane spanners

This page was built for publication: Lattice spanners of low degree

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