An O(n log n) Shortest Path Algorithm Based on Delaunay Triangulation

作者：Jan Gene Eu^*; Sun Chi Chia; Tsai Wei Chun; Lin Ting Hsiang

来源：IEEE/ASME Transactions on Mechatronics, 2014, 19(2): 660-666.

DOI：10.1109/TMECH.2013.2252076

• Delaunay triangulation
• Fermat points
• motion planning
• O(n log n)
• shortest path problem

In Euclidean and/or lambda-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.

• 出版日期2014-4