Narrow Results

We show that the Yao graph Y₄ in the L₂ metric is a spanner with stretch factor . Enroute to this, we also show that the Yao graph in the L_∞ metric is a plane spanner with stretch factor 8.

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₆.

Let S be a set of points in the plane, such that the unit disk graph with vertex set S is connected. We address the problem of finding orientations and a minimum radius for directional antennas of a fixed cone angle placed at the points of S, such that the induced communication graph G[S] is a hop t-spanner of the unit disk graph for S (meaning that G[S] is strongly connected, and contains a directed path with at most t edges between any pair of points within unit distance). We consider problem instances in which antenna angles are bounded below by 120° and 90°. We show that, in the case of 120° angles, a radius of 5 suffices to establish a hop 4-spanner; and in the case of 90° angles, a radius of 7 suffices to establish a hop 5-spanner.