Yao Graphs Span Theta Graphs

摘要

The Yao and Theta graphs are defined for a given point set and a fixed integer κ > 0. The space around each point is divided into k cones of equal angle, and each point is connected to a nearest neighbor in each cone. The difference between Yao and Theta graphs is in the way the nearest neighbor is defined: Yao graphs minimize the Euclidean distance between a point and its neighbor, and Theta graphs minimize the Euclidean distance between a point and the orthogonal projection of its neighbor on the bisector of the hosting cone. We prove that, corresponding to each edge of the Theta graph θ_6, there is a path in the Yao graph Y_6 whose length is at most 8.82 times the edge length. Combined with the result of Bonichon, Gavoille, Hanusse and Ilcinkas, who prove an upper bound of 2 on the stretch factor of θ_6, we obtain an upper bound of 17.7 on the stretch factor of Y_6.