Narrow Results

Yao and Theta graphs are defined for a given point set and a fixed integer k > 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 Θ₆, there is a path in the Yao graph Y₆ whose length is at most 8.82 times the edge length. Combined with the result of Bonichon et al., who prove an upper bound of 2 on the stretch factor of Θ₆, we obtain an upper bound of 17.64 on the stretch factor of Y₆.