We show that the Yao graph Y 4 in the L 2 metric is a spanner with stretch factor 8√2(26 + 23√2 ). Enroute to this, we also show that the Yao graph Y ∞4 in the L ∞ metric is a plane spanner with stretch factor 8.

Additional Metadata
Keywords spanner, Y4, Yao graph
Persistent URL dx.doi.org/10.1142/S0218195912600047
Journal International Journal of Computational Geometry and Applications
Citation
Bose, P, Damian, M. (Mirela), DouÏeb, K. (Karim), O'Rourke, J. (Joseph), Seamone, B. (Ben), Smid, M, & Wuhrer, S. (Stefanie). (2012). π/2-Angle yao graphs are spanners. In International Journal of Computational Geometry and Applications (Vol. 22, pp. 61–82). doi:10.1142/S0218195912600047