Jh. Reif et Ja. Storer, SINGLE-EXPONENTIAL UPPER BOUND FOR FINDING SHORTEST PATHS IN 3 DIMENSIONS, Journal of the Association for Computing Machinery, 41(5), 1994, pp. 1013-1019
We derive a single-exponential time upper bound for finding the shorte
st path between two points in 3-dimensional Euclidean space with (nonn
ecessarily convex) polyhedral obstacles. Prior to this work, the best
known algorithm required double-exponential time. Given that the probl
em is known to be PSPACE-hard, the bound we present is essentially the
best (in the worst-case sense) that can reasonably be expected.