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

Autor:	Galant, Damien, Pilatte, Cédric
Rok vydání:	2020
Předmět:	Computer Science - Computational Geometry
Druh dokumentu:	Working Paper
Popis:	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. Comment: 6 pages, 7 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2010.13473 Zobrazit plný text záznamu View this record from Arxiv