A single-exponential upper bound for finding shortest paths in three dimensions
John H. Reif, James A. Storer · Journal of the ACM · 1994
We derive a single-exponential time upper bound for finding the shortest path between two points in 3-dimensional Euclidean space with (nonnecessarily convex) polyhedral obstacles. Prior to this work, the best known algorithm required double-exponential time. Given that the problem is known to be PSPACE-hard, the bound we present is essentially the best (in the worst-case sense) that can reasonably be expected.