Information Technology Reference
In-Depth Information
On the Performance of Triangulation-Based
Multiple Shooting Method for 2D Geometric
Shortest Path Problems
Phan Thanh An 1 , 2 , Nguyen Ngoc Hai 3 , Tran Van Hoai 4 ,
and Le Hong Trang 1 , 5(
B
)
1 Instituto Superior Tecnico, CEMAT, Av. Rovisco Pais,
1049-001 Lisboa, Portugal
lhtrang@math.ist.utl.pt
2 Institute of Mathematics, 18 Hoang Quoc Viet road, 10307 Hanoi, Vietnam
3 Department of Mathematics, International University,
Vietnam National University, Thu Duc, Ho Chi Minh City, Vietnam
4 Faculty of Computer Science and Engineering, HCMC University of Technology,
268 Ly Thuong Kiet Street, Ho Chi Minh City, Vietnam
5 Faculty of Information Technology, Vinh University, 182 Le Duan,
Vinh, Vietnam
Abstract. In this paper we describe an algorithm based on the idea
of the direct multiple shooting method for solving approximately 2D
geometric shortest path problems (introduced by An et al. in Journal
of Computational and Applied Mathematics, 244 (2103), pp. 67-76).
The algorithm divides the problem into suitable sub-problems, and then
solves iteratively sub-problems. A so-called collinear condition for com-
bining the sub-problems was constructed to obtain an approximate solu-
tion of the original problem. We discuss here the performance of the
algorithm. In order to solve the sub-problems, a triangulation-based algo-
rithm is used. The algorithms are implemented by C++ code. Numerical
tests for An et al.'s algorithm are given to show that it runs significantly
in terms of run time and memory usage.
·
·
Keywords: Approximate algorithm
Multiple shooting method
Mem-
·
·
ory usage
Run time
Shortest path
1
Introduction
The problem of finding the Euclidean shortest path between two points in a
simple polygon is one of fundamental problems in computational geometry and
arises in many applications such as graph algorithms, geographic information sys-
tem (GIS), robotics, etc. (see [ 3 ]). There are many approximation algorithms for
An erratum to this chapter is available at DOI 10.1007/978-3-662-45947-8 8
c
 
 
Search WWH ::




Custom Search