A note on optimal degree-three spanners of the square lattice

Abstract

In this short note, we prove that the degree-three dilation of the square lattice ${\mathbb{Z}}^2$ is $1+\sqrt{2}$. This disproves a conjecture of Dumitrescu and Ghosh. We give a computer-assisted proof of a local-global property for the uncountable set of geometric graphs achieving the optimal dilation.

arXiv comment6 pages, 7 figures

References in corpus (1)

• The Stretch Factor of the Delaunay Triangulation Is Less Than 1.998