Flying over a polyhedral terrain

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 time and O(nlogn) 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 -factor approximation algorithm in Euclidean space, and a 2-approximation algorithm in the general Lp metric.