Fast marching method

The fast marching method is a <a href="/facts/Numerical_method/MrQIMSIY">numerical method</a> created by <a href="/facts/James_Sethian/pf1L9Gn5">James Sethian</a> for solving <a href="/facts/Boundary_value_problem/QEfmUqmP">boundary value problems</a> of the <a href="/facts/Eikonal_equation/ITjReqSB">Eikonal equation</a>:

|
        
        ∇
        u
        (
        x
        )
        
          |
        
        =
        1
        
          /
        
        f
        (
        x
        )
        
           for 
        
        x
        ∈
        Ω
      
    
    {\displaystyle |\nabla u(x)|=1/f(x){\text{ for }}x\in \Omega }

u
        (
        x
        )
        =
        0
        
           for 
        
        x
        ∈
        ∂
        Ω
      
    
    {\displaystyle u(x)=0{\text{ for }}x\in \partial \Omega }

Typically, such a problem describes the evolution of a closed surface as a function of time 
 
 
 
 u
 
 
 {\displaystyle u}
 
 with speed 
 
 
 
 f
 
 
 {\displaystyle f}
 
 in the normal direction at a point 
 
 
 
 x
 
 
 {\displaystyle x}
 
 on the propagating surface. The speed function is specified, and the time at which the contour crosses a point 
 
 
 
 x
 
 
 {\displaystyle x}
 
 is obtained by solving the equation. Alternatively, 
 
 
 
 u
 (
 x
 )
 
 
 {\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 
 
 
 
 x
 
 
 {\displaystyle x}
 
. The fast marching method takes advantage of this <a href="/facts/Optimal_control/9SmcQHjJ">optimal control</a> 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 <a href="/facts/Dijkstra%2527s_algorithm/ehun88jl">Dijkstra's algorithm</a> and uses the fact that information only flows outward from the seeding area. This problem is a special case of <a href="/facts/Level-set_method/jTDtmENI">level-set methods</a>. <a href="/facts/Eikonal_equation/ITjReqSB">More general algorithms exist</a> but are normally slower.
Extensions to non-flat (triangulated) domains solving

|
        
        
          ∇
          
            S
          
        
        u
        (
        x
        )
        
          |
        
        =
        1
        
          /
        
        f
        (
        x
        )
        ,
      
    
    {\displaystyle |\nabla _{S}u(x)|=1/f(x),}

for the surface 
 
 
 
 S
 
 
 {\displaystyle S}
 
 and 
 
 
 
 x
 ∈
 S
 
 
 {\displaystyle x\in S}
 
, were introduced by <a href="/facts/Ron_Kimmel/qf0QSHuj">Ron Kimmel</a> and <a href="/facts/James_Sethian/pf1L9Gn5">James Sethian</a>.

Fast marching method open-in-new

Fast marching method