Several published results [27??“30] were proposed to build
Delaunay triangulation or its relatives in a localized way.
Localized Delaunay Triangulation
Li et al [27, 28] gave a localized algorithm that constructs a sequence of
graphs, called a localized Delaunay
LDel(k)(V ), which are supergraphs of UDel(V ). We begin with some necessary
definitions before reviewing the algorithm. Triangle ?–?uvw is called a
k-localized Delaunay triangle if the interior of the circumcircle of ?–?uvw does
not contain any vertex of V that is a k-neighbor of u, v, or w; and all edges of
the triangle ?–?uvw have length no more than one unit. The k-localized Delaunay
graph over a vertex set V , denoted by LDel(k)(V ), has exactly all Gabriel
edges in UDG and edges of all k-localized Delaunay triangles.
The localized algorithm for the construction of LDel(k)(V ) goes as follows.
Each node u first gathers the location information of its k-hop neighbors
Nk(u) and computes the Delaunay triangulation Del(Nk(u)) of its k-neighbors
Nk(u), including u itself. Each node u marks all Gabriel edges uv incident on
u, which will never be deleted. Each node u finds all triangles ?–?uvw from
Del(Nk(u)) such that all three edges of ?–?uvw have length at most one unit.
If angle \wuv ?‰? ??
3 , node u broadcasts a message proposal(u, v,w) to form a
k-localized Delaunay triangle ?–?uvw in LDel(k)(V ), and listens to the messages
from other nodes.
Pages:
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206