Fast marching method – Wikipedia
From Wikipedia, the free encyclopedia
Algorithm for solving boundary value problems of the Eikonal equation
The fast marching method^{[1]} is a numerical method created by James Sethian for solving boundary value problems of the Eikonal equation:
Typically, such a problem describes the evolution of a closed surface as a function of time
${displaystyle u}$with speed
in the normal direction at a point
${displaystyle x}$on the propagating surface. The speed function is specified, and the time at which the contour crosses a point
${displaystyle x}$is obtained by solving the equation. Alternatively,
${displaystyle u(x)}$can be thought of as the minimum amount of time it would take to reach
${displaystyle partial Omega }$starting from the point
${displaystyle x}$. 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 and uses the fact that information only flows outward from the seeding area. This problem is a special case of levelset methods. More general algorithms exist but are normally slower.
Extensions to nonflat (triangulated) domains solving
for the surface
${displaystyle S}$and
${displaystyle xin S}$, were introduced by Ron Kimmel and James Sethian.

Maze as speed function shortest path

Distance map multistencils with random source points
Algorithm[edit]
First, assume that the domain has been discretized into a mesh. We will refer to meshpoints as nodes. Each node
${displaystyle x_{i}}$has a corresponding value
${displaystyle 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
${displaystyle mathbb {R} ^{n}}$, between
${displaystyle 1}$and
${displaystyle 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
 For every far node
 Let
 For every neighbor
 If
 If there exists a considered node, return to step 3. Otherwise, terminate.
See also[edit]
External links[edit]
 ^ J.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Natl. Acad. Sci., 93, 4, pp.1591–1595, 1996. [1]
Recent Comments