DocumentCode :
739558
Title :
Near-Shortest Path Planning on a Quadratic Surface With 
Time
Author :
Chi-Chia Sun ; Jan, Gene Eu ; Shao-Wei Leu ; Kai-Chieh Yang ; Yi-Chun Chen
Author_Institution :
Dept. of Electr. Eng., Nat. Formosa Univ., Huwei, Taiwan
Volume :
15
Issue :
11
fYear :
2015
Firstpage :
6079
Lastpage :
6080
Abstract :
An O(n log n) near-shortest path-planning algorithm based on the Delaunay triangulation, Ahuja-Dijkstra algorithm, and ridge points in the quadratic plane is presented. The shortest path planning is an NP-hard problem in the general 3-D space. Compared with the other O(n log n) time near-shortest path approach, the path length of the proposed method is 2.81% longer than the Kanai and Suzuki´s algorithm with 29 Steiner points, but the computation is 4,261 times faster. Notably, the proposed method is ideal for being extended to solve the path-planning problem on the mission planning of cruise missile.
Keywords :
computational complexity; mesh generation; path planning; Ahuja-Dijkstra algorithm; Delaunay triangulation; NP-hard problem; near-shortest path-planning algorithm; quadratic plane; quadratic surface; ridge points; Digital elevation models; Path planning; Planning; Sensors; Steiner trees; Time complexity; Digital Terrain Model; Motion Planning; Motion planning; Quadratic Surface; Ridge Points; Shortest Path- Planning; digital terrain model; quadratic surface; ridge points; shortest path-planning;
fLanguage :
English
Journal_Title :
Sensors Journal, IEEE
Publisher :
ieee
ISSN :
1530-437X
Type :
jour
DOI :
10.1109/JSEN.2015.2464271
Filename :
7177044
Link To Document :
