Fast marching method


The fast marching method is a numerical method created by James Sethian for solving boundary value problems of the Eikonal equation:
Typically, such a problem describes the evolution of a closed surface as a function of time with speed in the normal direction at a point on the propagating surface. The speed function is specified, and the time at which the contour crosses a point is obtained by solving the equation. Alternatively, can be thought of as the minimum amount of time it would take to reach starting from the point. The 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 domains solving
for the surface and, were introduced by Ron Kimmel and James Sethian.

Algorithm

First, assume that the domain has been discretized into a mesh. We will refer to meshpoints as nodes. Each node has a corresponding value.
The algorithm works just like Dijkstra's algorithm but differs in how the nodes' values are calculated. In Dijkstra's algorithm, a node's value is calculated using a single one of the neighboring nodes. However, in solving the PDE in, between and of the neighboring nodes are used.
Nodes are labeled as far, considered, and accepted.
  1. Assign every node the value of and label them as far; for all nodes set and label as accepted.
  2. For every far node, use the Eikonal update formula to calculate a new value for. If then set and label as considered.
  3. Let be the considered node with the smallest value. Label as accepted.
  4. For every neighbor of that is not-accepted, calculate a tentative value.
  5. If then set. If was labeled as far, update the label to considered.
  6. If there exists a considered node, return to step 3. Otherwise, terminate.