When a node u receives a message proposal(u, v,w), u
accepts the proposal of constructing ?–?uvw, if ?–?uvw belongs to the Delaunay
triangulation Del(Nk(u)), by broadcasting message accept(u, v,w); otherwise,
it rejects the proposal by broadcasting message reject(u, v,w). A node u adds
119
Yu Wang
the edges uv and uw to its set of incident edges if the triangle ?–?uvw is in
the Delaunay triangulation Del(Nk(u)) and both v and w have sent either
accept(u, v,w) or proposal(u, v,w).
It was proved that the graph constructed by the above algorithm is
LDel(k)(V ). Indeed, for each triangle ?–?uvw of LDel(k)(V ), one of its interior
angles is at least ??/3 and ?–?uvw is in Del(Nk(u)), Del(Nk(v)) and
Del(Nk(w)). So one of the nodes among {u, v,w} will broadcast the message
proposal(u, v,w) to form a k-localized Delaunay triangle ?–?uvw. As
Del(Nk(u)) is a planar graph, and a proposal is made only if \wuv ?‰? ??
3 ,
node u broadcasts at most six proposals. And each proposal is replied to by
at most two nodes. Therefore, the total communication cost (except messages
for gathering the information of k-hop neighbors) is O(n) messages.
As shown in [27, 28], the graph LDel(1)(V ) may contain some edges intersecting
while LDel(k)(V ) is a planar graph for any k ?‰? 2. Although LDel(1)(V )
is not a planar graph, [27] proved LDel(1)(V ) has thickness 2 which implies it
is sparse. Since UDel(V ) ??† LDel(k)(V ), which is proved in [27,28], LDel(k)(V )
is also a length spanner.
Pages:
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207