Approximate Shortest Path Calculations in Simple Polyhedra
Fajie Li, Reinhard Klette · 2008
Abstract. This paper considers the calculation of a Euclidean shortest path (ESP) in a three-dimensional (3D) polyhedral space Π. We propose an approximate κ(ε) · O(M|V |) 3D ESP algorithm (excluding preprocessing), with preprocessing time complexity O(M|E | + |S | + |V | log |V |), for solving a special, but ‘fairly general ’ case of the 3D ESP problem, where Π does not need to be convex, V and E are the sets of vertices and edges of Π, respectively, and S is the set of faces (triangles) of Π; M is the maximal number of vertices of a socalled critical polygon; κ(ε) = (L0 − L)/ε where L0 is the length of an initial path and L is the true (i.e., optimum) path length. The given algorithm solves approximately three (previously known to be) NP-complete or NP-hard 3D ESP problems in time κ(ε) · O(k), where k is the number of layers in a stack, which is introduced in this paper as being the problem environment. The proposed approximation method has straightforward applications for ESP problems when analyzing polyhedral objects (e.g., in 3D imaging), of for ‘flying ’ over a polyhedral terrain.