Pi/2-Angle Yao Graphs are Spanners
Authors:
- Prosenjit BosePBProsenjit Bose
- Mirela DamianMDMirela Damian
- Karim DouiebKDKarim Douieb
- Joseph O'RourkeJOJoseph O'Rourke
- Ben SeamoneBSBen Seamone
- Michiel SmidMSMichiel Smid
- Stefanie WuhrerSWStefanie Wuhrer
Preprint
Abstract
We show that the Yao graph Y4 in the L2 metric is a spanner with stretch factor 8(29+23sqrt(2)). Enroute to this, we also show that the Yao graph Y4 in the Linf metric is a planar spanner with stretch factor 8.Keywords
All Related Versions
This publication has 1 reference indexed in Scilit:
- Approximating geometric bottleneck shortest pathsComputational Geometry, 2004