Instead of using a circumcircle formed by the three robots on a triangle, a circumcircle
formed by the two robots on each edge of a triangle is used. This approach uses
a stricter test and yields a subset of edges of the Delaunay triangulation. Note that
this test is scalable because it can be accomplished with just one-hop communication.
Figure 3 shows the Delaunay Triangulation and its corresponding partial Delaunay
Triangulation based on the test in [35]. Correspondingly, a robot Ri??™s one-hop
neighbor are the robots that are directly connected to Ri in PDT. All the following
discussion and algorithms are applicable for both Delaunay triangulation and partial
Delaunay triangulation.
(a) Delaunay Triangulation (b) Partial Delaunay Triangulation
Fig. 3. Comparison of Delaunay Triangulation and partial Delaunay Triangulation for the same
set of generators.
Motivated by the adjacency matrix for a mobile sensor network [19], an adjacency
matrix, A(t), is defined to specify the connectivity of the Delaunay tessellation.
A(t) is a square matrix which is uniquely defined by the Delaunay triangulation.
Here Aij = di j if Ri and Rj are one-hop neighbors, otherwise Aij = 0. The ith
column of A(t), denoted by d(t) = {di 1, di 2, . . . , di n}T , defines the link proper-
??’100 ??’80 ??’60 ??’40 ??’20 0 20 40 60 80 100
??’100
??’80
??’60
??’40
??’20
0
20
40
60
80
100
??’100 ??’80 ??’60 ??’40 ??’20 0 20 40 60 80 100
??’100
??’80
??’60
??’40
??’20
0
20
40
60
80
100
70 Jindong Tan
ties of Ri and its one-hop neighboring robots.
Pages:
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141