Fast marching method: Difference between revisions

Revision as of 22:29, 16 February 2016

Revision as of 06:39, 17 February 2016

Line 1:

The '''fast marching method'''<ref name="sethian_fmm">J.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Nat. Acad. Sci., 93, 4, pp.1591--1595, 1996. [https://math.berkeley.edu/~sethian/2006/Papers/sethian.fastmarching.pdf]</ref> is a numerical method created by [[James Sethian]] for solving [[boundary_value_problem|boundary value problemsproblem]]s of the [[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(x)</math> in the normal direction at a point <math>x</math> on the propogatingpropagating 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>. 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 method]]s. [[Eikonal_equationEikonal equation#Computational_AlgorithmsComputational Algorithms|More general algorithms exist]] but are normally slower.

Extensions to non-flat (triangulated) domains solving:

::<math>|\nabla_S u(x)|=1 / f(x),

Line 25:

First, assume that the ___domain has been discretized into a mesh. We will refer to meshpoints 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 value of node's is 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 <math>\mathbb{R}^n</math> between <math>1</math> and <math>n</math> of the neighboring nodes [[Eikonal_equationEikonal equation#Numerical_ApproximationNumerical Approximation|are used]].

Nodes are labeled as <i>''far</i>'' (not yet visited), <i>''considered</i>'' (visited and value tentatively assigned), and <i>''accepted</i>'' (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 accepted node <math>x_i</math>, use the [[Eikonal_equationEikonal equation#Numerical_ApproximationNumerical Approximation|Eikonal update formula]] 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>.

Line 52:

==Notes==

{{Reflist}}

{{mathapplied-stub}}

[[Category:Numerical differential equations]]

{{mathapplied-stub}}