Shortest Paths On Convex Polytopes

So here I am, trying to get some sausage tasting in before I leave. I'm trying to hunt down a paper by Schreiber and Sharir on computing shortest paths exactly in three dimensions on a convex polytope.

The story of this problem is interesting. If the domain is arbitrary (three dimensions with arbitrary obstacles: think of a missile flying through a city), the problem is NP-hard (which is good if you're a pacifist). If you then restrict yourself to shortest paths on a convex polytope (now you're a snake on a really nice hill, trying to find some food), then the problem becomes easier.

Eons ago (well ok, back in 1986) Sharir and Schorr gave the first polynomial time algorithm for this problem. Their solution (runnning in n³ log n time) exploited a very neat fact about shortest paths on a convex surface; the so-called "unfolding" property.

suppose you draw a shortest path between two points on a convex surface, and then cut out the faces containing the path. If you unroll them onto a table, the path you drew would be a straight line. Voila !

This was subsequently improved. Mount used a "continuous Djikstra" method that expanded wavefronts from the start point, shaved the running time down to n² log n. This approach was generalized to non-convex polyhedra by Mitchell, Mount and Papadimitrious. in 1990, Chen and Han removed the log factor in the algorithm, using a different approach. That's where things stood for a long time (I'm ignoring other aspects of the story) till 1999, when Sanjeev Kapoor had a paper in STOC that claimed an n log²n running time for the problem.

Here's where things get strange: apparently no one (except the author, I imagine) believes that the paper is correct. There are numerous details left unspecified in the conference version, (Joe O'Rourke has made an attempt to explain what's going on), and to date there has been no journal version of this paper.

Which brings us to the paper I started off with. Schreiber and Sharir have a paper in this year's SoCG that presents an optimal algorithm for the shortest path problem on convex polytopes. Their algorithm runs in n log n time. The long version of the paper is now 131 pages and counting (!), and contains in an appendix an attempt at refuting aspects of Kapoor's algorithm.

Verifying the details of this algorithm will take some time, but at least there is a fully detailed manuscript available. Perhaps this will bring to an end the mystery surrounding the true complexity of the problem.

Aside: So I do a google search for "An efficient algorithm for shortest paths on a convex polytope in three dimensions", and the top links I find are for "Approximating shortest paths on a convex polytope in three dimensions". I guess approximations are more important after all.

Update (3/26/07): I recently received the following email from Sanjiv Kapoor and am reproducing it with his permission:

The single outstanding comment "apparently no one (except the author, I imagine) believes that the paper is correct" on your blog, is worrisome in its expansiveness -- (note that a blog is a public document)--

A more detailed (at least enough details from my viewpoint-) was available and never requested by anyone-- so I don't know if anyone even tried to seriously understand the method, apart from Joe O'Rourke and recentlly by SS. The only error which I myself found, has not been reported by anyone else as yet. The recent paper with Inkulu and Maheshwari gives an "improved" planar SP algorithm, which of course didnt make it to SOCG, but has crossed the 40 page single space) mark (if that is a measure of detailed correctness). In my original version I actively tried to omit all details which would require a few minutes thought--

He also encloses a mail from Yevgeny Schreiber which acknowledges his comments and modifies one of their examples claiming a problem with his algorithm. Yevgeny continues to mention technical details in the 1999 paper that remain unresolved, so this matter remains unsettled.