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.
Distance map multi-stencils with random source points
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 (not yet visited), considered (visited and value tentatively assigned), and accepted (visited and value permanently assigned).
Assign every node the value of and label them as far; for all nodes set and label as accepted.
For every far node , use the
Eikonal update formula to calculate a new value for . If then set and label as considered.
Let be the considered node with the smallest value . Label as accepted.
For every neighbor of that is not-accepted, calculate a tentative value .
If then set . If was labeled as far, update the label to considered.
If there exists a considered node, return to step 3. Otherwise, terminate.