A Fast Introduction to Fast Marching Methods and Level Set Methods

Overview

Fast Marching Methods and level set methods are numerical techniques designed to track the evolution of interfaces. Most numerical techniques attempt to follow moving boundaries by putting a collection of marker points on the evolving front and then changing their positions to correspond to the moving front. This approach has many problems associated with it.

In contrast, level set methods and Fast Marching Methods share a common view of how to solve these problems. Rather than focus on the moving boundaries themselves, these techniques exploit a strong link between moving interfaces and equations from computational fluid equations. The idea of building numerical methods around this link was first discussed in

Numerical Methods for Propagating Fronts : Sethian, J.A.,
in Variational Methods for Free Surface Interfaces, Eds. P. Concus and R. Finn, Springer-Verlag, NY, 1987.
"Most algorithms place marker particles along the front and advance the positions of the particles in accordance with a set of finite difference approximations to the equations of motion. Such schemes usually go unstable and blow up as the curvature builds around a cusp, since small errors in the position produce large errors in the determination of the curvature. One alternative is to consider the reformulation of the equations of motion as a conservation law with viscocity, and solve these equations with the techniques developed for gas dynamics. These techniques, based on high-order upwind formulations, are particularly attractive, since they are highly stable, accurate, and preserve monotonicity...."


This is the key idea. It has led to two different, yet complementary techniques for tracking evolving fronts:

  • An extremely efficient Fast Marching Method for certain specialized front problems.
  • A more general, but slower all-purpose time-dependent level set method.


Both methods are designed to handle problems in which the separating interfaces develop sharp corners and cusps, change topology, and become truly intricate.



The Key Ideas (Non-technical explanations)


An intuitive, non-technical explanation of each method:
  1. The general idea of Fast Marching Methods

  2. The general idea of Level Set Methods



If you want to know more


There are two general resources about these techniques.
  1. A popular magazine article that appeared in the American Scientist on the subject.
  2. A recent book on Level Set and Fast Marching Methods.
Additional technical publications may be found at on the publications page.


Return to Fast Marching/Level Set Main Page




J.A. Sethian
sethian@math.berkeley.edu You are visitor number to this page.