Improved bounds on the stretch factor of Y₄

详细信息    查看全文

• 作者：Mirela Damian ; ^{mirela.damian@villanova.edu} ; Naresh Nelavalli ^{nnelaval@villanova.edu}
• 关键词：Cone graph ; Yao ; Four cones ; Theta ; Spanner
• 刊名：Computational Geometry
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：62
• 期：Complete
• 页码：14-24
• 全文大小：419 K
• 卷排序：62

文摘

We establish an upper bound of 13+82≲4.931 on the stretch factor of the Yao graph Y4∞ defined in the L∞L∞-metric, improving upon the best previously known upper bound of 6.31. We also establish an upper bound of (11+72)4+22≲54.62 on the stretch factor of the Yao graph Y4Y4 defined in the L2L2-metric, improving upon the best previously known upper bound of 663.