# Fast marching method

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Fast_marching_method
> Markdown URL: https://mediated.wiki/source/Fast_marching_method.md
> Source: https://en.wikipedia.org/wiki/Fast_marching_method
> Source revision: 1253508517
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{short description|Algorithm for solving boundary value problems of the Eikonal equation}}

The '''fast marching method'''<ref name="sethian_fmm">J.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Natl. Acad. Sci., 93, 4, pp.1591--1595, 1996. [https://math.berkeley.edu/~sethian/2006/Papers/sethian.fastmarching.pdf]</ref> is a [numerical method](/source/numerical_method) created by [James Sethian](/source/James_Sethian) for solving [boundary value problem](/source/boundary_value_problem)s of the [Eikonal equation](/source/Eikonal_equation):

: <math>|\nabla u(x)|=1/f(x) \text{ for } x \in \Omega</math>
: <math>u(x) = 0 \text{ for } x \in \partial \Omega</math>

Typically, such a problem describes the evolution of a closed surface as a function of time <math>u</math> with speed <math>f</math> in the normal direction at a point <math>x</math> on the propagating surface. The speed function is specified, and the time at which the contour crosses a point <math>x</math> is obtained by solving the equation. Alternatively, <math>u(x)</math> can be thought of as the minimum amount of time it would take to reach <math>\partial\Omega</math> starting from the point <math>x</math>. The fast marching method takes advantage of this [optimal control](/source/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](/source/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 method](/source/level-set_method)s. [More general algorithms exist](/source/Eikonal_equation) but are normally slower.

Extensions to non-flat (triangulated) domains solving

::<math>|\nabla_S u(x)|=1 / f(x),
</math>
 
for the surface <math>S</math> and <math>x\in S</math>, were introduced by [Ron Kimmel](/source/Ron_Kimmel) and [James Sethian](/source/James_Sethian).

<gallery>
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
</gallery>

==Algorithm==

First, assume that the domain has been discretized into a mesh. We will refer to mesh points as nodes. Each node <math>x_i</math> has a corresponding value <math>U_i = U(x_i) \approx u(x_i)</math>.

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](/source/Partial_differential_equation) in <math>\mathbb{R}^n</math>, between <math>1</math> and <math>n</math> of the neighboring nodes [are used](/source/Eikonal_equation).

Nodes are labeled as ''far'' (not yet visited), ''considered'' (visited and value tentatively assigned), and ''accepted'' (visited and value permanently assigned).

# Assign every node <math>x_i</math> the value of <math>U_i=+\infty</math> and label them as ''far''; for all nodes <math>x_i \in \partial\Omega</math> set <math>U_i = 0</math> and label <math>x_i</math> as ''accepted''.
# For every far node <math>x_i</math>, use the [Eikonal update formula](/source/Eikonal_equation) to calculate a new value for <math>\tilde{U}</math>. If <math>\tilde{U} < U_i</math> then set <math>U_i = \tilde{U}</math> and label <math>x_i</math> as ''considered''.
# Let <math>\tilde{x}</math> be the considered node with the smallest value <math>U</math>. Label <math>\tilde{x}</math> as ''accepted''.
# For every neighbor <math>x_i</math> of <math>\tilde{x}</math> that is not-accepted, calculate a tentative value <math>\tilde{U}</math>.
# If <math>\tilde{U} < U_i </math> then set <math>U_i = \tilde{U}</math>. If <math>x_i</math> 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](/source/Level-set_method)
* [Fast sweeping method](/source/Fast_sweeping_method)
* [Bellman–Ford algorithm](/source/Bellman%E2%80%93Ford_algorithm)

==External links==
* [https://www.mit.edu/~jnt/dijkstra.html Dijkstra-like Methods for the Eikonal Equation J.N. Tsitsiklis, 1995]
* [http://math.berkeley.edu/~sethian/ The Fast Marching Method and its Applications by James A. Sethian]
* [https://web.archive.org/web/20110719232108/http://mecca.louisville.edu/~msabry/projects/msfm.htm Multi-Stencils Fast Marching Methods] 
* [http://www.mathworks.com/matlabcentral/fileexchange/24531 Multi-Stencils Fast Marching Matlab Implementation]
* [http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/841/pdf/imm841.pdf Implementation Details of the Fast Marching Methods]
* [https://rd.springer.com/article/10.1007/s11075-008-9183-x Generalized Fast Marching method] by Forcadel et al. [2008] for applications in image segmentation.
* [https://github.com/scikit-fmm/scikit-fmm Python Implementation of the Fast Marching Method]
*See Chapter 8 in [http://etd.fcla.edu/CF/CFE0001159/Rumpf_Raymond_C_200608_PhD.pdf Design and Optimization of Nano-Optical Elements by Coupling Fabrication to Optical Behavior] {{Webarchive|url=https://web.archive.org/web/20130820063106/http://etd.fcla.edu/CF/CFE0001159/Rumpf_Raymond_C_200608_PhD.pdf |date=2013-08-20 }}

==Notes==
{{Reflist}}

Category:Numerical differential equations

---
Adapted from the Wikipedia article [Fast marching method](https://en.wikipedia.org/wiki/Fast_marching_method) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Fast_marching_method?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.