Fast marching method

The fast marching method is a numerical method created by James Sethian for solving boundary value problems of the Eikonal equation:

$|\nabla u(x)|=1/f(x){\text{ for }}x\in \Omega$

$u(x)=0{\text{ for }}x\in \partial \Omega$

Typically, such a problem describes the evolution of a closed surface as a function of time $u$ with speed $f(x)$ in the normal direction at a point $x$ on the propogating surface. The speed function is specified, and the time at which the contour crosses a point $x$ is obtained by solving the equation. Alternatively, $u(x)$ can be thought of as the minimum amount of time it would take to reach $\partial \Omega$ starting from the point $x$. Fast marching method takes advantage of this optimal control interpretation of the problem in order to build a solution outwards starting from the "known information", i.e. the boundary values.

The algorithm is similar to Dijkstra's algorithm and uses the fact that information only flows outward from the seeding area. This problem is a special case of level set methods. More general algorithms exist but are normally slower.

Extensions to non-flat (triangulated) domains solving:

$|\nabla _{S}u(x)|=1/f(x),\,\,{\mbox{for the surface}}\,\,S,\,{\mbox{and}}\,\,x\in S.$

was introduced by Ron Kimmel and James Sethian.

• 
  Maze as speed function shortest path
• 
  Distance map multi-stencils with random source points

See also

• Level set method
• Fast sweeping method
• Bellman-Ford algorithm

External links

• Djikstra-like Methods for the Eikonal Equation J.N. Tsitsiklis, 1995
• The Fast Marching Method and its Applications by James A. Sethian
• Multi-Stencils Fast Marching Methods
• Multi-Stencils Fast Marching Matlab Implementation
• Implementation Details of the Fast Marching Methods
• Generalized Fast Marching method by Forcadel et al. [2008] for applications in image segmentation.
• See Chapter 8 in Design and Optimization of Nano-Optical Elements by Coupling Fabrication to Optical Behavior