Flying over a Polyhedral Terrain

Abstract. We consider the problem of computing shortest paths in three-dimensions in the presence of a single-obstacle polyhedral terrain, and present a new algorithm that for any p ≥ 1, computes a (c + ε)-approximation to the Lp-shortest path above a polyhedral terrain in O(n ε log n log log n) time and O(n logn) space, where n is the number of vertices of the terrain, and c = 2(p−1)/p. This leads to a FPTAS for the problem in L1 metric, a ( 2 + ε)-factor approximation algorithm in Euclidean space, and a 2-approximation algorithm in the general Lp metric.