Towards Tight Bounds on Theta-Graphs

Abstract

We present improved upper and lower bounds on the spanning ratio of $\theta$-graphs with at least six cones. Given a set of points in the plane, a $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta =2\pi /m$, and adds an edge to the `closest' vertex in each cone. We show that for any integer $k\ge 1$, $\theta$-graphs with $4k+2$ cones have a spanning ratio of $1+2\sin (\theta /2)$ and we provide a matching lower bound, showing that this spanning ratio tight. Next, we show that for any integer $k\ge 1$, $\theta$-graphs with $4k+4$ cones have spanning ratio at most $1+2\sin (\theta /2)/(\cos (\theta /2)-\sin (\theta /2))$. We also show that $\theta$-graphs with $4k+3$ and $4k+5$ cones have spanning ratio at most $\cos (\theta /4)/(\cos (\theta /2)-\sin (3\theta /4))$. This is a significant improvement on all families of $\theta$-graphs for which exact bounds are not known. For example, the spanning ratio of the $\theta$-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 $\theta$-routing algorithm. In particular, we show that the $\theta$-routing algorithm is $(1+2\sin (\theta /2)/(\cos (\theta /2)-\sin (\theta /2)))$-competitive on $\theta$-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 $\theta$-graphs. In particular, we show that $\theta$-graphs with $4k+4$ cones have spanning ratio at least $1+2\tan (\theta /2)+2{\tan }^2(\theta /2)$. This is somewhat surprising since, for equal values of $k$, the spanning ratio of $\theta$-graphs with $4k+4$ cones is greater than that of $\theta$-graphs with $4k+2$ cones, showing that increasing the number of cones can make the spanning ratio worse.

arXiv admin note: text overlap with arXiv:1401.2127