Lattice spanners of low degree

Abstract

Let ${\delta }_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+\sqrt{2}\le {\delta }_0(\Lambda ,3)\le (3+2\sqrt{2})5^{-1/2}=2.6065\dots$ and ${\delta }_0(\Lambda ,4)=\sqrt{2}$. If $\Lambda$ is the infinite hexagonal lattice, it is shown that ${\delta }_0(\Lambda ,3)=1+\sqrt{3}$ and ${\delta }_0(\Lambda ,4)=2$. All our constructions are planar lattice tilings constrained to degree $3$ or $4$.

17 pages, 13 figures; A preliminary version in: Proceedings of the 2nd International Conference on Algorithms and Discrete Applied Mathematics, Thiruvananthapuram, India, Febr. 2016, vol $9602$ of LNCS

Cited by in corpus (1)

• Towards Plane Spanners of Degree 3