20130812
On the spanning ratio of thetagraphs
Publication
Publication
We present improved upper bounds on the spanning ratio of a large family of θgraphs. A θgraph partitions the plane around each vertex into m disjoint cones, each having aperture θ = 2 π/m. We show that for any integer k ≥ 1, θgraphs with 4k + 4 cones have spanning ratio at most 1 + 2 sin(θ/2) / (cos(θ/2)  sin(θ/2)). We also show that θgraphs with 4k + 3 and 4k + 5 cones have spanning ratio at most cos(θ/4) / (cos(θ/2)  sin(3θ/4)). This is a significant improvement on all families of θgraphs for which exact bounds are not known. For example, the spanning ratio of the θgraph with 7 cones is decreased from at most 7.5625 to at most 3.5132. We also improve the upper bounds on the competitiveness of the θrouting algorithm for these graphs to 1 + 2 sin(θ/2) / (cos(θ/2)  sin(θ/2)) on θgraphs with 4k + 4 cones and to 1 + 2 sin(θ/2)·cos(θ/4) / (cos(θ/2)  sin(3θ/4)) on θgraphs with 4k + 3 and 4k + 5 cones. For example, the routing ratio of the θgraph with 7 cones is decreased from at most 7.5625 to at most 4.0490.
Additional Metadata  

Keywords  θgraphs, computational geometry, spanners, spanning ratio 
Persistent URL  dx.doi.org/10.1007/9783642401046_16 
Citation 
Bose, P, Van Renssen, A. (André), & Verdonschot, S. (Sander). (2013). On the spanning ratio of thetagraphs. doi:10.1007/9783642401046_16
