Description: |
Wireless nodes are often powered by batteries and have limited memory resources. These characteristics make it critical to compute and maintain, at each node, only a subset of neighbors that the node communicates with. These subsets of neighbors define a topology and the problem of choosing "appropriate" subsets of neighbors is called the topology control problem . Highly relevant to the topology control problem is the class of Yao graphs, defined as follows. Let P be a set of points in the plane. The Yao graph Y k ( P ), for k > 2, is defined as follows. At each point u ∈ P , any k equal-separated rays originated at u define k cones; in each non-empty cone C u , pick the shortest edge { u, v } connecting u to its nearest neighbor v ∈ C u (breaking ties arbitrarily), and add { u, v } to Y k . For a fixed value t ≥ 1, a graph G embedded in the plane is a length t -spanner if, for all pairs of vertices u, v ∈ P , the shortest path in G from u to v is no longer than t · | uv |; here | uv | denotes the Euclidean distance between u and v . It is a standing open question to decide whether the Yao structure Y k , for k ≤ 5, is a length t -spanner or not, for some constant t . We make progress towards resolving this question by showing that Y 4 is a length spanner for sets of points in convex position. We prove that Y 2 and Y 3 are not length spanners. We show that a related structure, called Yao-Yao, is a length spanner for any set of points of bounded aspect ratio (defined as the ratio between the largest to the smallest interpoint distances). |