Fast marching method

<h2 id="algorithm">Algorithm</h2>
<p>First, assume that the domain has been discretized into a mesh. We will refer to mesh points as nodes. Each node 
  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
  
 has a corresponding value 
  
    
      
        
          U
          
            i
          
        
        =
        U
        (
        
          x
          
            i
          
        
        )
        ≈
        u
        (
        
          x
          
            i
          
        
        )
      
    
    {\displaystyle U_{i}=U(x_{i})\approx u(x_{i})}
  
.
</p><p>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 <a href="/facts/Partial_differential_equation/DyPsBlv7">PDE</a> in 
  
    
      
        
          
            R
          
          
            n
          
        
      
    
    {\displaystyle \mathbb {R} ^{n}}
  
, between 
  
    
      
        1
      
    
    {\displaystyle 1}
  
 and 
  
    
      
        n
      
    
    {\displaystyle n}
  
 of the neighboring nodes <a href="/facts/Eikonal_equation/ITjReqSB">are used</a>.
</p><p>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).
</p>
<ol><li>Assign every node 
  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
  
 the value of 
  
    
      
        
          U
          
            i
          
        
        =
        +
        ∞
      
    
    {\displaystyle U_{i}=+\infty }
  
 and label them as <i>far</i>; for all nodes 
  
    
      
        
          x
          
            i
          
        
        ∈
        ∂
        Ω
      
    
    {\displaystyle x_{i}\in \partial \Omega }
  
 set 
  
    
      
        
          U
          
            i
          
        
        =
        0
      
    
    {\displaystyle U_{i}=0}
  
 and label 
  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
  
 as <i>accepted</i>.</li>
<li>For every far node 
  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
  
, use the <a href="/facts/Eikonal_equation/ITjReqSB">Eikonal update formula</a> to calculate a new value for 
  
    
      
        
          
            
              U
              ~
            
          
        
      
    
    {\displaystyle {\tilde {U}}}
  
. If 
  
    
      
        
          
            
              U
              ~
            
          
        
        <
        
          U
          
            i
          
        
      
    
    {\displaystyle {\tilde {U}}<U_{i}}
  
 then set 
  
    
      
        
          U
          
            i
          
        
        =
        
          
            
              U
              ~
            
          
        
      
    
    {\displaystyle U_{i}={\tilde {U}}}
  
 and label 
  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
  
 as <i>considered</i>.</li>
<li>Let 
  
    
      
        
          
            
              x
              ~
            
          
        
      
    
    {\displaystyle {\tilde {x}}}
  
 be the considered node with the smallest value 
  
    
      
        U
      
    
    {\displaystyle U}
  
. Label 
  
    
      
        
          
            
              x
              ~
            
          
        
      
    
    {\displaystyle {\tilde {x}}}
  
 as <i>accepted</i>.</li>
<li>For every neighbor 
  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
  
 of 
  
    
      
        
          
            
              x
              ~
            
          
        
      
    
    {\displaystyle {\tilde {x}}}
  
 that is not-accepted, calculate a tentative value 
  
    
      
        
          
            
              U
              ~
            
          
        
      
    
    {\displaystyle {\tilde {U}}}
  
.</li>
<li>If 
  
    
      
        
          
            
              U
              ~
            
          
        
        <
        
          U
          
            i
          
        
      
    
    {\displaystyle {\tilde {U}}<U_{i}}
  
 then set 
  
    
      
        
          U
          
            i
          
        
        =
        
          
            
              U
              ~
            
          
        
      
    
    {\displaystyle U_{i}={\tilde {U}}}
  
. If 
  
    
      
        
          x
          
            i
          
        
      
    
    {\displaystyle x_{i}}
  
 was labeled as <i>far</i>, update the label to <i>considered</i>.</li>
<li>If there exists a <i>considered</i> node, return to step 3. Otherwise, terminate.</li></ol>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Level-set_method/jTDtmENI">Level-set method</a></li>
<li><a href="/facts/Fast_sweeping_method/ClRzWXMm">Fast sweeping method</a></li>
<li><a href="/facts/Bellman%25E2%2580%2593Ford_algorithm/Sx6INcdr">Bellman–Ford algorithm</a></li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.mit.edu/~jnt/dijkstra.html">Dijkstra-like Methods for the Eikonal Equation J.N. Tsitsiklis, 1995</a></li>
<li><a href="http://math.berkeley.edu/~sethian/">The Fast Marching Method and its Applications by James A. Sethian</a></li>
<li><a href="https://web.archive.org/web/20110719232108/http://mecca.louisville.edu/~msabry/projects/msfm.htm">Multi-Stencils Fast Marching Methods</a></li>
<li><a href="http://www.mathworks.com/matlabcentral/fileexchange/24531">Multi-Stencils Fast Marching Matlab Implementation</a></li>
<li><a href="http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/841/pdf/imm841.pdf">Implementation Details of the Fast Marching Methods</a></li>
<li><a href="https://rd.springer.com/article/10.1007/s11075-008-9183-x">Generalized Fast Marching method</a> by Forcadel et al. [2008] for applications in image segmentation.</li>
<li><a href="https://github.com/scikit-fmm/scikit-fmm">Python Implementation of the Fast Marching Method</a></li>
<li>See Chapter 8 in <a href="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</a> <a href="https://web.archive.org/web/20130820063106/http://etd.fcla.edu/CF/CFE0001159/Rumpf_Raymond_C_200608_PhD.pdf">Archived</a> 2013-08-20 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a></li></ul>
<h2 id="notes">Notes</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>J.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Natl. Acad. Sci., 93, 4, pp.1591--1595, 1996. [1] <a href="https://math.berkeley.edu/~sethian/2006/Papers/sethian.fastmarching.pdf" target="_blank">https://math.berkeley.edu/~sethian/2006/Papers/sethian.fastmarching.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Fast marching method open-in-new

Fast marching method