On the Spanning Ratio of Constrained Yao-Graphs.
André van Renssen · 2014
We present upper bounds on the spanning ratio of con-strained Yao-graphs with at least 7 cones. Given a set of points in the plane, a Yao-graph partitions the plane around each vertex into k disjoint cones, each having aperture θ = 2pi/k, 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. We show that constrained Yao-graphs with an even number of cones (k ≥ 8) have spanning ratio at most 1 / (1 − 2 sin(θ/2)) and constrained Yao-graphs with an odd number of cones (k ≥ 7) have spanning ratio at most 1 / (1 − 2 sin(3θ/8)). These bounds match the current upper bounds in the unconstrained setting. 1