Towards tight bounds on theta-graphs: More is not always better
We present improved upper and lower bounds on the spanning ratio of θ-graphs with at least six cones. Given a set of points in the plane, a θ-graph partitions the plane around each vertex u into m disjoint cones, each having aperture θ = 2π/m, and adds an edge in each cone to the vertex whose projection onto the bisector of that cone is closest to u. We show that for any integer k≥1, θ-graphs with 4k+ 2 cones have a spanning ratio of 1 + 2 sin (θ/2) and we provide a matching lower bound, showing that this spanning ratio is tight.Next, 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. These spanning proofs also imply improved upper bounds on the competitiveness of the θ-routing algorithm. In particular, we show that the θ-routing algorithm is (1 + 2 sin (θ/2)/(cos (θ/2) - sin (θ/2)))-competitive on θ-graphs with 4k + 4 cones and that this ratio is tight.Finally, we present improved lower bounds on the spanning ratio of these graphs. Using these bounds, we provide a partial order on these families of θ-graphs. In particular, we show that θ-graphs with 4k + 4 cones have spanning ratio at least 1+2tan (θ/2)+2tan2(θ/2), where θ is 2π/(4k+4). This is surprising since, for equal values of k, the spanning ratio of θ-graphs with 4k+4 cones is greater than that of θ-graphs with 4k+2 cones, showing that increasing the number of cones can make the spanning ratio worse.
|Keywords||Computational geometry, Spanners, Spanning ratio, Theta-graphs, Tight bounds|
|Journal||Theoretical Computer Science|
Bose, P, De Carufel, J.-L. (Jean-Lou), Morin, P, van Renssen, A. (André), & Verdonschot, S. (Sander). (2016). Towards tight bounds on theta-graphs: More is not always better. Theoretical Computer Science, 616, 70–93. doi:10.1016/j.tcs.2015.12.017