Title :
An
Shortest Path Algorithm Based on Delaunay Triangulation
Author :
Jan, Gene Eu ; Chi-Chia Sun ; Wei Chun Tsai ; Ting-Hsiang Lin
Author_Institution :
Dept. of Electr. Eng., Nat. Taipei Univ., Taipei, Taiwan
Abstract :
In Euclidean and/or λ-geometry planes with obstacles, the shortest path problem involves determining the shortest path between a source and a destination. There are three different approaches to solve this problem in the Euclidean plane: roadmaps, cell decomposition, and potential field. In the roadmaps approach, a visibility graph is considered to be one of the most widely used methods. In this paper, we present a novel method based on the concepts of Delaunay triangulation, an improved Dijkstra algorithm and the Fermat points to construct a reduced visibility graph that can obtain the near-shortest path in a very short amount of computational time. The length of path obtained using our algorithm is the shortest in comparison to the other fastest algorithms with O(n log n) time complexity. The proposed fast algorithm is especially suitable for those applications which require determining the shortest connectivity between points in the Euclidean plane, such as the robot arm path planning and motion planning for a vehicle.
Keywords :
computational complexity; computational geometry; graph theory; mesh generation; λ-geometry planes; Delaunay triangulation; Euclidean plane; Fermat points; O(n log n) shortest path algorithm; O(n log n) time complexity; cell decomposition; improved Dijkstra algorithm; potential field; reduced visibility graph; roadmaps approach; robot arm path planning; vehicle motion planning; $O(nlog n)$; Delaunay triangulation; Fermat points; motion planning; shortest path problem;
Journal_Title :
Mechatronics, IEEE/ASME Transactions on
DOI :
10.1109/TMECH.2013.2252076