Spanning Properties of Yao and $\Theta$-Graphs in the Presence of Constraints

Abstract

We present improved upper bounds on the spanning ratio of constrained $\theta$-graphs with at least 6 cones and constrained Yao-graphs with 5 or at least 7 cones. Given a set of points in the plane, a Yao-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. Constrained Yao-graphs have the additional property that no edge properly intersects any of the given line segment constraints. Constrained $\theta$-graphs are similar to constrained Yao-graphs, but use a different method to determine the closest vertex. We present tight bounds on the spanning ratio of a large family of constrained $\theta$-graphs. We show that constrained $\theta$-graphs with $4k+2$ ($k\ge 1$ and integer) cones have a tight spanning ratio of $1+2\sin (\theta /2)$, where $\theta$ is $2\pi /(4k+2)$. We also present improved upper bounds on the spanning ratio of the other families of constrained $\theta$-graphs. These bounds match the current upper bounds in the unconstrained setting. We also show that constrained Yao-graphs with an even number of cones ($m\ge 8$) have spanning ratio at most $1/(1-2\sin (\theta /2))$ and constrained Yao-graphs with an odd number of cones ($m\ge 5$) have spanning ratio at most $1/(1-2\sin (3\theta /8))$. As is the case with constrained $\theta$-graphs, these bounds match the current upper bounds in the unconstrained setting, which implies that like in the unconstrained setting using more cones can make the spanning ratio worse.