HOME

OVERVIEW

APPLICATIONS

INTERACTIVE APPLETS

HISTORY OF THE METHODS/FLOW CHART

PUBLICATIONS

EDUCATIONAL MATERIAL

ACKNOWLEDGEMENTS

ABOUT THE AUTHOR/CV

















Copyright:
1996, 1999, 2006
J.A. Sethian

Applications to Geodesics
You are currently in the
topic outlined in red. 		Overview of and references for papers on theory Overview of and references for papers on link to hyperbolic equations Overview of and references for level_set methods Overview of and references for on stationary formulation Overview of and references for Narrow Band formulation Overview of and references for papers on Fast Marching Methods Work on unstructured mesh versions of level set and fast marching methods Coupling interface methods to complex physics Adaptive mesh refinement Applications to semiconductor modeling Applications to geometry Applications to medical imaging Applications to constructing geodesics on surfaces Applications to seismology and travel times Applications to combustion Applications to fluid mechanics Applications to materials sciences Applications to robotics Applications to computer graphics Applications to CAD/CAM Applications to mesh generation

Click on navigable flow chart to go to new topic

click on any text
to go to a new topic.



Fast Marching Methods can be used to construct geodesic shortest paths on manifolds. The idea is relatively straightforward, once one has a Fast Marching Method on unstructured meshes. Imagine one wants the shortest geodesic path on surface between points A and B. If one solves the Eikonal equation
| nabla T | = 1

with boundary condition that T=0 at A, then once an arrival time T is computed at the point B, one can trace backwards along the gradient nabla T to produce the shortest geodesic path. This is what is done in Ref. 1 below. We refer the reader to more details and examples of geodesic shortest paths.


New Book and Resource on Level Set and Fast Marching Methods




Examples:
Shortest path geodesic on sinusoidal surface. See Ref. 1 below.



References:

  1. Fast Marching Methods on Triangulated Domains : Kimmel, R., and Sethian, J.A., Proceedings of the National Academy of Sciences, 95, pp. 8341-8435, 1998.
    Abstract

    The Fast Marching Method is a numerical algorithm for solving the Eikonal equation on a rectangular orthogonal mesh in O(M \log M) steps, where M is the total number of grid points. In this paper we extend the Fast Marching Method to triangulated domains with the same computational complexity. As an application, we provide an optimal time algorithm for computing the geodesic distances and thereby extracting shortest paths on triangulated manifolds.

    Download publications