Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
add comment

1 Answer

up vote 3 down vote accepted

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.
Polyhedron
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.

share|improve this answer
    
Thanks for the response - the Chen-Han algorithm looks like it will work for my purposes. –  Nick Alger Nov 4 '10 at 16:48
    
@mm225: Good. I wrote an abstract on this: "An Implementation of Chen & Han's Shortest Paths Algorithm," cs.smith.edu/~orourke/papers.php#28 –  Joseph O'Rourke Nov 4 '10 at 20:29
    
Hah, looks like I already found your paper on google and started reading it before you posted 0_o –  Nick Alger Nov 4 '10 at 20:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.