Improved Bounds on the Stretch Factor of Y₄

2016/02/17 by Damian, Mirela, Nelavalli, Naresh
#Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #I.1.2

paper · doi:10.48550/arxiv.1602.05481

Abstract

We establish an upper bound of 4.94 on the stretch factor of the Yao graph Y₄^∞ defined in the L_∞-metric, improving upon the best previously known upper bound of 6.31. We also establish an upper bound of 54.62 on the stretch factor of the Yao graph Y₄ defined in the Euclidean metric, improving upon the best previously known upper bound of 662.16.

Related

• An Infinite Class of Sparse-Yao Spanners
• The Yao Graph Y₅ is a Spanner
• Average Stretch Factor: How Low Does It Go?
• On the stretch factor of the Theta-4 graph
• Almost All Even Yao-Yao Graphs Are Spanners