The fast marching methodJ.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Natl. Acad. Sci., 93, 4, pp.1591--1595, 1996 /ref> is a numerical method created by
James Sethian
James Albert Sethian is a professor of mathematics at the University of California, Berkeley and the head of the Mathematics Grouat the United States Department of Energy, United States Department of Energy's Lawrence Berkeley National Laborat ...
Eikonal equation
An eikonal equation (from Greek εἰκών, image) is a non-linear first-order partial differential equation that is encountered in problems of wave propagation.
The classical eikonal equation in geometric optics is a differential equation of ...
:
:
:
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
Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...
and uses the fact that information only flows outward from the seeding area. This problem is a special case of
level-set method
Level-set methods (LSM) are a conceptual framework for using level sets as a tool for numerical analysis of surfaces and shapes. The advantage of the level-set model is that one can perform numerical computations involving curves and surfaces o ...
s. More general algorithms exist but are normally slower.
Extensions to non-flat (triangulated) domains solving
::
for the surface and , were introduced by
Ron Kimmel
Ron Kimmel ( he, רון קימל, b. 1963) is a professor of Computer Science and Electrical and Computer Engineering (by courtesy) at the Technion Israel Institute of Technology. He holds a D.Sc. degree in electrical engineering (1995) from the ...
and
James Sethian
James Albert Sethian is a professor of mathematics at the University of California, Berkeley and the head of the Mathematics Grouat the United States Department of Energy, United States Department of Energy's Lawrence Berkeley National Laborat ...
.
Image:Fast_marching_maze.png, Maze as speed function shortest path
Image:Fast_marching_multi_stencil_2nd_order.png, 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.
See also
*
Level-set method
Level-set methods (LSM) are a conceptual framework for using level sets as a tool for numerical analysis of surfaces and shapes. The advantage of the level-set model is that one can perform numerical computations involving curves and surfaces o ...
*
Fast sweeping method In applied mathematics, the fast sweeping method is a numerical method for solving boundary value problems of the Eikonal equation.
: , \nabla u(\mathbf), = \frac 1 \text \mathbf \in \Omega
: u(\mathbf) = 0 \text \mathbf \in \partial \Omega ...
*
Bellman–Ford algorithm
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.
It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it i ...