Approximate ESPs in Simple Cubic Polytopes Using a Rubberband Algorithm

Let p and q be two points inside a special type of cubic polytope Π. This paper provides a rubberband algorithm for computing a Euclidean shortest path between p and q (3D ESP) that is contained inside Π. The algorithm has κ1(ε) · κ2(ε) · O(n 2) time complexity, where n is the number of cubes consists of Π, κi(ε) = (L0i−Li)/ε, for the true length Li of some shortest path with initial (polygonal path) length L0i (used when approximating this shortest path), for i = 1, 2. Rubberband algorithms follow a straightforward design strategy, and the proposed algorithm is easy to implement and thus of importance for applications. The given rubberband algorithm can also be applied to solve approximately three NPcomplete or NP-hard 3D Euclidean shortest path (ESP) problems in time κ(ε) × O(k), where k is the number of layers in a stack which contains the defined obstacles. 1