Spanning Properties of Yao and -Graphs in the Presence of Constraints
We present improved upper bounds on the spanning ratio of constrained -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 = 2p/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 -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 -graphs. We show that constrained -graphs with 4k + 2 (k ≥ 1 and integer) cones have a tight spanning ratio of 1 + 2sin(/2), where is 2p/(4k + 2). We also present improved upper bounds on the spanning ratio of the other families of constrained -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 ≥ 8) have spanning ratio at most 1/(1 - 2sin(/2)) and constrained Yao-graphs with an odd number of cones (m ≥ 5) have spanning ratio at most 1/(1 - 2sin(3/8)). As is the case with constrained -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.
|Keywords||constraints, geometric graphs, Spanners, spanning ratio, tight bounds|
|Journal||International Journal of Computational Geometry and Applications|
Bose, P, & Van Renssen, A. (André). (2019). Spanning Properties of Yao and -Graphs in the Presence of Constraints. International Journal of Computational Geometry and Applications, 29(2), 95–120. doi:10.1142/S021819591950002X