What are some algorithms used for finding the shortest path between 2 points on a (riemannian) manifold (the manifold may have a smooth boundary)?
So far I've had 3 ideas, none of which seem that good:
1) (Rubber band principle) Find any path between the two points, then draw the path taut like a stretched rubber band with some damping.
2) (Ray-tracing analog) Shoot out geodesic rays from one point in all directions. If a ray hits the target, we're done. If the ray hits the boundary and is not close to tangent, ignore it. If the ray hits the boundary approximately tangent, then follow the geodesic on the boundary in that direction, shooting tangent rays off occasionally.
3) (Discretization) Triangulate/tetrahedralize/etc the manifold, and construct a weighted graph where the nodes correspond to the centerpoints of each tetrahedron, the edges correspond to tetrahedra that touch, and the weights correspond to the distance between tetrahedra centers. Then compute the shortest path in the graph.
Most of the stuff I've seen in the literature is concerned with the theoretical existence of the path rather than actually computing it. How do you find the shortest path in practice?
Best Answer
There are many algorithms for computing shortest paths on polyhedral 2-manifolds. With a student I computed the shortest paths shown below with one, the Chen-Han algorithm. The algorithms fan out shortest paths to a frontier, mimicking the structure (but not the details) of Dijkstra's algorithm for shortest paths in a graph. Sometimes the method is called the "continuous Dijkstra" method. These algorithms (all in $\mathbb{R}^3$) are described in many places, including the book Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Chapter 24.
I would assume the same approach will work for triangulated manifolds in arbitrary dimensions, but of course it will be significantly more complicated to implement.