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?