On Shortest Paths Amidst Convex Polyhedra
Micha Sharir · SIAM Journal on Computing · 1987
Let K be a 3-D convex polyhedron having n vertices. A sequence $\xi $ of edges of K is called a shortest-path sequence if there exist two points X, Y on the surface S of K such that is the sequence of edges crossed by the shortest path from X to Y along S. We show that the number of shortest-path sequences for K is polynomial in n, and as a consequence prove that the shortest path between two points in 3-space which must avoid the interiors of a fixed number of disjoint convex polyhedral obstacles, can be calculated in time polynomial in the total number of vertices of these obstacles (but exponential in the number of obstacles).