Finding shortest paths is a fundamental operator in spatial databases, which has a wide range of applications to both academia and industry. Although shortest path problems in graphs and planes are well-studied, there are not much studies about finding shortest paths on terrain surfaces. Besides, only a few related studies consider the slope of paths....[ Read more ]

Finding shortest paths is a fundamental operator in spatial databases, which has a wide range of applications to both academia and industry. Although shortest path problems in graphs and planes are well-studied, there are not much studies about finding shortest paths on terrain surfaces. Besides, only a few related studies consider the slope of paths.

In this thesis, we propose an algorithm for finding slope-constrained shortest paths or simply finding shortest gentle paths on terrain surfaces. The algorithm guarantees that the slope of the path does not exceed a maximum slope value defined by users, and the length of the path is the shortest among all such paths. Since traditional surface shortest paths can be viewed as shortest gentle paths with a maximum slope value equal to π/2, our problem is more general than the traditional surface shortest path problem. Besides, in some applications where time is a critical factor, a much faster (1 + ∈)-approximate algorithm is also proposed.

The algorithms are evaluated with both real terrain data sets including Eagle Peak (Wyoming State, U.S.A) and Bearhead (Washington State, U.S.A) and synthetic data sets.