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 paper 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 \mbox{$2+\sqrt{3} \approx 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$.     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.
['Luis Barba', 'Prosenjit Bose', 'Mirela Damian', 'Rolf Fagerberg', 'Wah Loon Keng', "Joseph O'Rourke", 'André van Renssen', 'Perouz Taslakian', 'Sander Verdonschot', 'Ge Xia']
New and improved spanning ratios for Yao graphs