# Algorithm for shortest path on manifold

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?

-
How is the manifold given? –  Mariano Suárez-Alvarez Nov 3 '10 at 5:55
I'm interested in the answer to the question in general (n-dimensional, general reimannian manifold, etc), but right now it's as follows: 1) the user draws a series of polygonal regions and subregions in the plane, 2) they can "glue" subregions with the same number of points together, 3) They can color in the shapes with varying brightness to represent the scalar curvature. –  Nick Alger Nov 3 '10 at 6:17
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.