The Delaunay triangulation defines the link properties between
one-hop neighbors, which are defined by a set of edges E = {di j(t), i, j =
1, 2, . . . , n, i 6= j}. The distance between one-hop neighbors, di j , can be estimated
by using local positioning systems or global positioning systems.
respectively. The multiple robotic vehicle system can be modeled as a large-dimensional
Chapter 3 A Scalable Graph Model and Coordination Algorithms 69
In a large scale system, a huge amount of communication and computation is required
to calculate the Delaunay Triangulation. In a distributed system, it is desirable
to use a localized algorithm for the graph model [1], [27], [35]. Each robot calculate
its own local Delaunay Triangulation by communicating only with the nodes within
its communication range. The robots may construct different Delaunay triangulation
locally because of the limited visibility or communication ranges. The union of local
Delaunay triangulations is a superset of the Delaunay triangulation. A robot communicates
with other robots to eliminate the inconsistent edges. A circumcircle test
by communicating with neighboring robots will eliminate the inconsistency edges
and generate a Partial Delaunay Triangulations(PDT). As shown in Figure 3, some
edges are lost in partial Delaunay triangulation due to the visibility of communication.
In [35], a simple test is used to generate partial Delaunay triangulation locally.
Pages:
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140