SHORTEST PATHS ON A POLYTOPE

Biliana Kaneva

I implemented an algorithm to find the shortest paths from a given source point on the surface of a convex polyhedron to all its vertices. The algorithm, due to Chen and Han, has been known for five years, but it has not been reliably implemented. I am following the work of an earlier Smith student, Diana Xu '96, who wrote the first implementation of the algorithm for her honors thesis under Professor O'Rourke. Her code, however, was numerically unstable.

We developed a new, more robust approach, and testing shows the code to be very reliable. An example of the output of my code is shown in the figure below. The shortest path from the source to each of the 100 vertices is drawn on the surface.

I am extending the implementation to handle nonconvex surfaces for my honors thesis.

Advisor: Joseph O'Rourke

This work was supported by the National Science Foundation.