A triangle is
118
Chapter 5 Topology Control for Wireless Sensor Networks
called the Delaunay triangle if its circumcircle is empty of vertices of V . See
Figure 2 (c) for an illustration.
Dobkin et al. [25] first proved the Delaunay Triangulation is a length spanner
with length stretch factor bounded by 1+???5
2 ??. Then Keil and Gutwin [26]
improved the constant to be 2??
3 cos( ??
6 ) = 4???3
9 ?? ?‰? 2.42. Notice that the Gabriel
graph is a subgraph of the Delaunay triangulation and the power stretch factor
of a Gabriel graph is 1. Thus, the power stretch factor of Delaunay triangulation
is also one, due to the monotonic property of the power spanner.
Given a set of points V , let UDel(V ) be the graph obtained by removing
all edges of Del(V ) that are longer than one unit, i.e., UDel(V ) = Del(V ) ??© UDG(V ). Li et al [27] considered the unit Delaunay triangulation UDel(V )
for planar spanner of UDG and proved that UDel(V ) is a 4???3
9 ??-spanner of
UDG(V ).
Though Delaunay triangulation (or unit Delaunay triangulation) is a wellknown
planar spanner, it is not appropriate to require the construction of the
Delaunay triangulation in the wireless communication environment because of
the possible massive communications it requires. Notice that the circumcircle
of a triangle can be very large (much larger than the transmission range of
a sensor node), therefore it may need global information to build the Delaunay
triangulation.
Pages:
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205