• Fast Introduction
  • Level Set Methods
  • Fast Marching Methods
  • Ordered Upwind Methods








    J.A. Sethian


    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 for tracking interfaces by exploting this link was discussed in

    Numerical Methods for Propagating Fronts : Sethian, J.A., in Variational Methods for Free Surface Interfaces, Proceedings 1985 Vallambrosa Conference, 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 idea forms one cornerstone of partial differential equations based numerical methods for tracking evolving fronts. It has contributed to two different, yet complementary techniques for tracking evolving fronts: (1) An extremely efficient Fast Marching Method for certain specialized front problems. (2) 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. Their virtues are most on display in problems in three dimensions (or more) in which interface motion is intricately bound up with complex physics and geometry.

    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.
    2. A recent book on Level Set and Fast Marching Methods.
    Additional technical publications may be found at on the publications page.