An $\bm{O(n\log n)}$ Shortest Path Algorithm Based on Delaunay Triangulation

摘要

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.