HOME

TheInfoList



OR:

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 In numerical analysis, a numerical method is a mathematical tool designed to solve numerical problems. The implementation of a numerical method with an appropriate convergence check in a programming language is called a numerical algorithm. Mathem ...
created by James Sethian for solving
boundary value problem In mathematics, in the field of differential equations, a boundary value problem is a differential equation together with a set of additional constraints, called the boundary conditions. A solution to a boundary value problem is a solution to t ...
s of the Eikonal equation: : , \nabla u(x), =1/f(x) \text x \in \Omega : u(x) = 0 \text x \in \partial\Omega Typically, such a problem describes the evolution of a closed surface as a function of time u with speed f in the normal direction at a point x on the propagating surface. The speed function is specified, and the time at which the contour crosses a point x is obtained by solving the equation. Alternatively, u(x) can be thought of as the minimum amount of time it would take to reach \partial\Omega starting from the point x. The fast marching method takes advantage of this
optimal control Optimal control theory is a branch of mathematical optimization that deals with finding a control for a dynamical system over a period of time such that an objective function is optimized. It has numerous applications in science, engineering and ...
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 (triangulated) domains solving ::, \nabla_S u(x), =1 / f(x), for the surface S and x\in S, were introduced by Ron Kimmel and James Sethian. 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 x_i has a corresponding value U_i = U(x_i) \approx u(x_i). 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 \mathbb^n, between 1 and n 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 x_i the value of U_i=+\infty and label them as ''far''; for all nodes x_i \in \partial\Omega set U_i = 0 and label x_i as ''accepted''. # For every far node x_i, use the Eikonal update formula to calculate a new value for \tilde. If \tilde < U_i then set U_i = \tilde and label x_i as ''considered''. # Let \tilde be the considered node with the smallest value U. Label \tilde as ''accepted''. # For every neighbor x_i of \tilde that is not-accepted, calculate a tentative value \tilde. # If \tilde < U_i then set U_i = \tilde. If x_i 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 * Fast sweeping method * Bellman–Ford algorithm


External links


Dijkstra-like Methods for the Eikonal Equation J.N. Tsitsiklis, 1995

The Fast Marching Method and its Applications by James A. Sethian



Multi-Stencils Fast Marching Matlab Implementation

Implementation Details of the Fast Marching Methods

Generalized Fast Marching method
by Forcadel et al. 008for applications in image segmentation.
Python Implementation of the Fast Marching Method
*See Chapter 8 i
Design and Optimization of Nano-Optical Elements by Coupling Fabrication to Optical Behavior


Notes

{{Reflist Numerical differential equations