Pi/2-Angle Yao Graphs are Spanners

Authors:
  • PBProsenjit Bose
    Prosenjit Bose
  • MDMirela Damian
    Mirela Damian
  • KDKarim Douieb
    Karim Douieb
  • JOJoseph O'Rourke
    Joseph O'Rourke
  • BSBen Seamone
    Ben Seamone
  • MSMichiel Smid
    Michiel Smid
  • SWStefanie Wuhrer
    Stefanie Wuhrer

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.

This publication has 1 reference indexed in Scilit: