New and Improved Spanning Ratios for Yao Graphs

Luis Barba, Prosenjit Bose, Mirela Damian +7

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…