Fast Marching Methods are the optimal way to solve the Eikonal equation

F | nabla T (x,y,z) | = 1

which arise in a variety of applications, including front propagation problems in which a front propagates normal to itself with a speed F which depends only on position and is always positive. This includes applications in optics, seismology, path planning and robotic navigation, photolitography and electromagnetics. Introduced in Ref. 1 below, they produce the first arrival viscosity solution of the stationary Hamilton-Jacobi equation.
The techniques rely on upwind schemes, the theory of viscosity solutions, causality, and sort algorithms borrowed from computer science. They compute the solution to the Eikonal equation in O(N log N) steps, where N is the total number of points in the computational domain. As well as providing optimal techniques for solving a collection of physical problems, they also provide ways of building and computing extension velocities which are required to couple level set methods to complex physics.

( A general introduction, images, and movies about Fast Marching Methods )

Connections to other works:

The Fast Marching Method evolved in part from examining the limit of the narrow band method as the band was reduced to one grid cell. Fast Marching Methods, by taking the perspective of the large body of work on higher order upwind, finite difference approximants from hyperbolic conservation laws, allow for higher order versions on both structured and unstructured meshes. At their core, Fast Marching Methods are most closely related to Dijkstra's method (Ref. 4), which is a classic algorithm for computing the shortest path on a network of links. It too relies on a heap to find the smallest element of the expanding front, and can be thought of as a Huyghen's principle algorithm where the expanding wave is confined to the network paths. It can also be thought of as an upwind finite difference scheme, however the equation it is solving is not the same as the Eikonal equation, and hence the paths it produces are non-unique, unlike the Fast Marching Method. The Fast Marching Method is an upwind finite difference scheme which produces the correct viscosity solution to the Eikonal equation through a causality relationship based on the order of the upwinding. Tsitsikilis (Ref. 5) developed a control theory approach (as opposed to the Fast Marching upwind finite difference perspective) to solving the Eikonal equation that is also a viscosity solution with the same operation count. This leads to a causality relationship based on the optimality criterion rather than on the upwind finite difference operators employed in Fast Marching Methods. In the particular special case of a first order upwind finite difference for the Fast Marching Method on a square mesh, the resulting update equation at each grid point can be seen to be the same quadratic equation obtained through Tsitsikilis's control theoretic approach.

Annotated References:

• Ref #1 below introduces Fast Marching Methods, discusses the causality relationship and heap structure which gives the method its underlying speed, and applies it to problems in photolithography development.
  
  
• Ref. #2 further discusses the technique, and applies it to a host of applications.
  
  
• Ref. #3 shows how to build higher order Fast Marching Methods, using switch functions and higher order stencils; it tests the accuracy of these algorithms on several examples.

New Book and Resource on Level Set and Fast Marching Methods



References:

1. A Fast Marching Level Set Method for Monotonically Advancing Fronts : Sethian, J.A., Proc. Nat. Acad. Sci., 93, 4, pp.1591-1595, 1996.

   Abstract

   We present a fast marching level set method for monotonically advancing fronts, which leads to an extremely fast scheme for solving the Eikonal equation. Level set methods are numerical techniques for computing the position of propagating fronts. They rely on an initial value partial differential equation for a propagating level set function, and use techniques borrowed from hyperbolic conservation laws. Topological changes, corner and cusp development, and accurate determination of geometric properties such as curvature and normal direction are naturally obtained in this setting. In this paper, we describe a particular case of such methods for interfaces whose speed depends only on local position. The technique works by coupling work on entropy conditions for interface motion, the theory of viscosity solutions for Hamilton-Jacobi equations and fast adaptive narrow band level set methods. The technique is applicable to a variety of problems, including shape-from-shading problems, lithographic development calculations in microchip manufacturing, and arrival time problems in control theory.

   Download publications

   
   
2. Theory, Algorithms, and Applications of Level Set Methods for Propagating Interfaces, : Sethian, J.A., Acta Numerica, Cambridge University Press, 1996.

   Abstract

   We review recent work on level set methods for following the evolution of complex interfaces. These techniques are based on solving an initial value partial differential equations for a level set functions, using techniques borrowed from hyperbolic conservation laws. Topological changes, corner and cusp development, and accurate determination of geometric properties such as curvature and normal direction are naturally obtained in this setting. The methodology results in robust, accurate, and efficient numerical algorithms for propagating interfaces in highly complex settings. We review the basic theory and approximations, describe a hierarchy of fast methods, including an extremely fast marching level set scheme for monotonically advancing fronts, based on a stationary formulation of the problem, and discuss extensions to multiple interfaces and triple points. Finally, we demonstrate the technique applied to a series of examples from geometry, material science and computer vision, including mean curvature flow, minimal surfaces, grid generation, fluid mechanics, and combustion.

   Download publications

   
   
3. Fast Marching Methods : Sethian, J.A., SIAM Review, 41, July, 1999

   Abstract

   Fast Marching Methods are numerical schemes for computing the solution of the non-linear Eikonal equation and related static Hamilton-Jacobi equations. They provide consistent, accurate, and highly efficient techniques, and are based on entropy-satisfying upwind schemes and fast sorting techniques. The computational complexity of the algorithms is $O(N \log N)$, where $N$ is the total number of points in the domain. These schemes are of use in a variety of applications, including problems in shape offsetting, computing distances from complex curves and surfaces, shape-from-shading, photolithography development, computing first arrivals in seismic travel times, construction of shortest geodesics on surfaces, optimal path planning around obstacles, and visibility and reflection calculations. In this paper, we review the development of these techniques, including the theoretical and numerical underpinnings, provide details of the computational schemes, and demonstrate the techniques in a collection of different areas.

   Download publications

   
   
   
4. A Note on Two Problems in Connection with Graphs, : Dijkstra, E.W., Numerische Mathematic, 1:269--271, 1959.
   
   
5. Efficient Algorithms for Globally Optimal Trajectories : Tsitsiklis, J.N., IEEE Transactions on Automatic Control, Volume 40, pp. 1528-1538, 1995.

Return to Fast Marching/Level Set Main Page