Approximate shortest path on a polyhedral surface and its applications

A new algorithm is proposed for calculating the approximate shortest path on a polyhedral surface. The method mainly uses Dijkstra's algorithm and is based on selective refinement of the discrete graph of a polyhedron. Although the algorithm is an approximation, it has the significant advantages of being fast and easy to implement, it has high approximation accuracy, and is numerically robust. The approximation accuracy and computation time are compared between this approximation algorithm and the extended Chen and Han (ECH) algorithm that can calculate the exact shortest path for non-convex polyhedra. The approximation algorithm can calculate shortest paths within 0.4% accuracy approximately 100-1000 times faster than the ECH algorithm in our examples. Two applications of the approximation algorithm to geometric modeling are discussed. (C) 2001 Elsevier Science Ltd. All rights reserved.