Near-Shortest Path Planning on a Quadratic Surface With <inline-formula> <tex-math notation="LaTeX">$O(n\log n)$ </tex-math></inline-formula> Time

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.