Approximate Shortest Path Calculations in Simple Polyhedra

Abstract

This paper considers the calculation of a Euclidean shortest path (ESP) in a three-dimenisonal (3D) polyhedral space II. We propose an approximate K(E).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 II; M is the maximal number of vertices of a so-called critical polygon; K(E)=(Lo-L)/E where Lo is the length of the 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 K(E).O(k) where k is the number of layers in a stack, which is introduced in this paper as the problem environment. The proposed approximation method is only an example of a general technique, for which the authors also see further potentials to support e cient approximate solutions for more general 3D ESP problems.