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θ=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≥1k≥1, θ  -graphs with 4k+24k+2 cones have a spanning ratio of 1+2sin⁡(θ/2)1+2sin⁡(θ/2) and we provide a matching lower bound, showing that this spanning ratio is tight.Next, we show that for any integer k≥1k≥1, θ  -graphs with 4k+44k+4 cones have spanning ratio at most 1+2sin⁡(θ/2)/(cos⁡(θ/2)−sin⁡(θ/2))1+2sin⁡(θ/2)/(cos⁡(θ/2)−sin⁡(θ/2)). We also show that θ  -graphs with 4k+34k+3 and 4k+54k+5 cones have spanning ratio at most cos⁡(θ/4)/(cos⁡(θ/2)−sin⁡(3θ/4))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+2sin⁡(θ/2)/(cos⁡(θ/2)−sin⁡(θ/2)))(1+2sin⁡(θ/2)/(cos⁡(θ/2)−sin⁡(θ/2)))-competitive on θ  -graphs with 4k+44k+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+44k+4 cones have spanning ratio at least 1+2tan⁡(θ/2)+2tan2⁡(θ/2)1+2tan⁡(θ/2)+2tan2⁡(θ/2), where θ   is 2π/(4k+4)2π/(4k+4). This is surprising since, for equal values of k, the spanning ratio of θ  -graphs with 4k+44k+4 cones is greater than that of θ  -graphs with 4k+24k+2 cones, showing that increasing the number of cones can make the spanning ratio worse.