Finding shortest gentle paths on polyhedral terrains by the method of multiple shooting

摘要

The problem of finding shortest 0-gentle paths can be stated as follows: given two points p, q on a polyhedral terrain and a slope parameter 0 e (0, n /2), the objective is to find a path joining p and q on the terrain which is shortest such that the slope of the path does not exceed 0. In this paper, we introduce some geometric and analysis properties of such paths and answer the question of whether known results of classical shortest paths hold for shortest 0-gentle paths. An algorithm for approximately computing such shortest 0-gentle paths on terrains is presented, where an approximate shortest 0-gentle path joining two points is a 0-gentle path whose length is the infimum of a sequence of that of 0-gentle paths in which they are decreasing. We also show that the sequence of lengths of paths obtained by the proposed algorithm is convergent. The algorithm is implemented in C++ using CGAL and Open GL in some specific circumstances.