Shortest Paths in a Cuboidal World

Abstract

Since 1987 it is known that the Euclidean shortest path problem is NP-hard. However, if the 3D world is subdivided into cubes, all of the same size, defining obstacles or possible spaces to move in, then the Euclidean shortest path problem has a linear-time solution, if all spaces to move in form a simple cube-curve. The shortest path through a simple cube-curve in the orthogonal 3D grid is a minimum-length polygonal curve (MLP for short). So far only one general and linear (only with respect to measured run times) algorithm, called the {\it rubberband algorithm}, was known for an approximative calculation of an MLP. The algorithm is basically defined by moves of vertices along critical edges (i.e., edges in three cubes of the given cube-curve). A proof, that this algorithm always converges to the correct MLP, and if so, then always (provable) in linear time, was still an open problem so far (the authors had successfully treated only a very special case of simple cube-curves before). In a previous paper, the authors also showed that the original rubberband algorithm required a (minor) correction. This paper finally answers the open problem: by a further modification of the corrected rubberband algorithm, it turns into a provable linear-time algorithm for calculating the MLP of any simple cube-curve. The paper also presents an alternative provable linear-time algorithm for the same task, which is based on moving vertices within faces of cubes. For a disticntion, we call the modified original algorithm now the {\it edge-based rubberband algorithm}, and the second algorithm is the {\it face-based rubberband algorithm}; the time complexity of both is in ${\cal O}(m)$, where $m$ is the number of critical edges of the given simple cube-curve.