New and Improved Spanning Ratios for Yao Graphs

Abstract

For a set of points in the plane and a fixed integer $k > 0$, the Yao graph $Y_k$ partitions the space around each point into $k$ equiangular cones of angle $ Θ =2π/k$, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of $Y_5$, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd $k ≥ 5$, the spanning ratio of $Y_k$ is at most $1/(1-2sin(3Θ/8))$, which gives the first constant upper bound for $Y_5$, and is an improvement over the previous bound of $1/(1-2sin(Θ/2))$ for odd $k ≥ 7$. We further reduce the upper bound on the spanning ratio for $Y_5$ from $10.9$ to $2+ sqrt(3) ≈ 3.74$, which falls slightly below the lower bound of $3.79$ established for the spanning ratio of $Θ_5$ ($Θ$-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and $Θ$-graph with the same number of cones. We also give a lower bound of $2.87$ on the spanning ratio of $Y_5$. In addition, we revisit the $Y_6$ graph, which plays a particularly important role as the transition between the graphs ($k > 6$) for which simple inductive proofs are known, and the graphs ($k łeq 6$) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of $Y_6$ from $17.6$ to $5.8$, getting closer to the spanning ratio of 2 established for $Θ_6$. Finally, we present the first lower bounds on the spanning ratio of Yao graphs with more than six cones, and a construction that shows that the Yao-Yao graph (a bounded-degree variant of the Yao graph) with five cones is not a spanner.

Publication
Journal of Computational Geometry