On the Performance of Triangulation-Based Multiple Shooting Method for 2D Geometric Shortest Path Problems - Transactions on Large-Scale Data-and Knowledge-Centered Systems - page 51

Find the shortest path between x and y in the polygon bounded by P , Q ,

and cutting segments ʾ and μ in which x ∈ ʾ and y ∈ μ .

end procedure
As mentioned, in [ 1 ] a shortest path algorithm based on incremental convex hull
was used. We, however, use alternatively the algorithm described in subsection 2.2 .
Following is the algorithm, based on the idea of the multiple shooting method, for
solving approximately the geometric shortest path problem in a simple polygon.

Algorithm 1 Multiple Shooting Method for 2D Shortest Path Problems

Input: vertices a and b of a simple polygon , respectively) is

the polyline formed by vertices of the polygon from a to b ( b to a , respectively)
in counterclockwise order.
Output: an approximate shortest path

PQ , where P ( Q

Z between a and b in PQ .

1. Divide the polygon PQ into suitable T i by cutting segments ʾ 1 ,...,ʾ k . Set

j = 0. Choose initial points a i ∈ ʾ i ,for i =1 ,...,k .

a i

, a i +1 , ʾ i , ʾ i +1 to get shortest path

Z i between a i and a i +1 2. Call SP

Z i in satisfy simultaneously the multiple shooting structure,

i.e., the collinear condition holds true, then goto 4 .
Otherwise, refine shooting points a i ∈

T i . Check if all

ʾ i to ensure that the collinear condition

holds true.
3. j = j +1, goto 2 .
4. return

∪ i =1 Z i Z := .

The Hausdorff distance between two sets A and B in 2D, denoted by d H ( A, B ),
is defined by

d H ( A, B ) = max { sup

x∈A

y∈B

inf x − y , sup

y∈B

x∈A

inf x − y } .

By means of Hausdorff distance, the Algorithm 1 gives an appropriate shortest
path between two points a and b in

D by the following.

Theorem 3 ([ 1 ]). Assume that a and b are points in a simple polygon D

and x i ∈ SP ( a, b ) ,i =0 , 1 ,...,k +1 ,x 0 = a, x k +1 = b .If a i ∈D such that

[ a i ,x i ] ↂD , 0 ≤ i ≤ k +1 , then

d H ∪ k +1

=1 SP ( a i− 1 ,a i ) ,SP ( a, b ) ≤

2 max

+1

x i − a i .

i

0 ≤i≤k

2.4 Numerical Example

The algorithms are implemented in C++ code and run on Ubuntu Linux oper-
ating system with platform Intel Core i3, CPU 530 3.0HGz x 4. Fig. 4 shows a
simple example of the shortest path between the vertex of smallest x -coordinate,
denoted by a , and the vertex of largest x -coordinate, denoted by b , in the mono-
tone polygon PQ

of 40 vertices.