Wireless Sensor Networks

80 Chapter 3 Networking Sensors

would be considered for inclusion in H. We will denote the resulting

subgraphs by RNG(G) and Gabriel(G). The good news is that both

can be computed by simple local algorithms (assuming that a pair of

nodes within distance 1 can talk to each other); the bad news is that

it is known that neither is always a spanner for G [23]—they are just

too sparse for that.

The Delaunay triangulation is known to be both planar (or course,

being a triangulation) and a spanner [54, 113] (best-known stretch

factor = 2.42) of the complete Euclidean graph on V. However, the

Delaunay triangulation is globally defined. For a local version, we can

consider a subgraph U consisting only of Delaunay edges of V whose

length is at most 1. This subgraph ...