New and Improved Spanning Ratios for Yao Graphs

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 $$\theta=2\pi/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 talk, we close this gap by showing that for odd $$k \geq 5$$, the spanning ratio of $$Y_k$$ is at most $$1/(1-2\sin(3\theta/8))$$, which gives the first constant upper bound for $$Y_5$$, and is an improvement over the previous bound of $$1/(1-2\sin(\theta/2))$$ for odd $$k \geq 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 $$\Theta_5$$ ($$\Theta$$-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 $$\Theta$$-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 \le 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 $$\Theta_6$$.