Improved Spanning Ratio of Theta-Five Revisited
Darryl Hill
Carleton University
This is a repeat of a talk given earlier in year, with a slight improvement in proof technique and (hopefully) a large improvement in clarity. The Theta-five graph was shown to be a 9.96-spanner by Bose et al., using a proof by induction on the size of an isosceles triangle defined by two points $a$ and $b$. We improve this bound to 5.70 using a proof by induction on the Euclidean distance between $a$ and $b$. This gives us a finer grained analysis while maintaining a comparable complexity, bringing us closer to the lower bound of 3.798.