×

Approximate shortest descending paths. (English) Zbl 1298.65031

This paper presents an approximation algorithm for the combination of a path length optimization and height constraints problem. Finding a shortest path on a terrain with monotonically decreasing height along this path from a source to a destination is described here. The input terrain is a polygonal surface created by triangular faces in 3D space projected injectively onto the \((x,y)\)-plane. Vertices of the terrain are considered to be the given source and destination. The presented shortest descending paths algorithm is \((1+\varepsilon)\)-approximate, running time is polynomial in \(n\) and \(\log(1/\varepsilon)\), and independent of the terrain geometry. A constant-factor lower bound on the optimal path length is computed and the quasi-length of a path is introduced. This is critical in both the design of the algorithm and the analysis of the approximation ratio. A new concept of quasi-length introduction can be useful for other path problems on polygonal surfaces. The developed algorithm can be applied in robotics, geographic information systems, when solving optimization problems in computational geometry, etc.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI Link