Information Technology Reference
In-Depth Information
The values
s
i
=
y
(
x
i
) of the solution
y
(
x
) of the problem are computed by
iteration, for
i
=1
,...,k
. In order to obtain the solution of the original problem,
a solution of the initial-value problem
y
=
f
(
x, y
)
,
for
x
∈
[
x
i
,x
i
+1
)
,
y
(
x
i
)=
s
i
,
is determined, denoted by
y
(
x
;
x
i
,s
i
), for
i
=1
,...,k
. Then by the continuity of
y
(
x
), the problem now is to determine
s
i
,for
i
=1
,...,k
, such that the following
conditions are satisfied (see Fig.
1
),
s
i
+1
=
y
(
x
i
+1
;
x
i
,s
i
)
,
for
i
=1
,...,k
−
1
,
y
(
b
)=
s
k
,
r
s
1
,s
k
=0
.
Because
y
(
x
) is differentiable on [
a, b
], if the continuity condition is satisfied at
x
i
, then
y
−
(
x
i
+1
;
x
i
,s
i
)=
y
+
(
x
i
+1
;
x
i
+1
,s
i
+1
)
,
where
y
−
(
x
i
)and
y
+
(
x
i
) denote the left and right derivatives of
y
(
x
)at
x
i
,
respectively, for
i
=1
,...,k
2. This means that the left and right tangent
lines to the graph of
y
(
x
) are collinear at the exact solution point (
x
i
,s
i
)
(see Fig.
1
).
The idea of continuity and differentiability of the multiple shooting method
leads us to define a so-called collinear condition in Subsection
2.3
.
−
2.2 A Triangulation-Based Algorithm for Finding Shortest Paths
in Sub-polygons
Algorithm given in [
1
] is based on the idea of the direct multiple shooting method
which is a variant of the multiple shooting approach for solving optimal con-
trol problems [
4
]. The algorithm divides a polygon into suitable sub-polygons.
A procedure is called to determine the shortest paths in the sub-polygons. An
algorithm based on incremental convex hull was used for the procedure. In this
paper, in order to analyze the performance of the algorithm we use instead the
funnel algorithm (see [
7
,
8
,
10
]). A triangulation of the polygon and graph theory
are required for the funnel algorithm. These are crucial factors that effect to the
performance of the algorithm for finding the geometric shortest paths.
For the funnel algorithm we first triangulate the polygon. Once the triangu-
lation of polygon is determined, a dual tree of the triangulation is constructed
based on the adjacent relationship between triangles of the triangulation. On the
dual tree, a sequence of consecutive triangles, i.e., two adjacent triangles of the
sequence share an edge, is determined so that the shortest path between starting
point
a
and destination point
b
is contained inside the sequence. The sequence
is said to be a
sleeve
. Each sharing edge of the sequence is said to be a
diagonal
Search WWH ::
Custom Search