HOME

OVERVIEW

APPLICATIONS

INTERACTIVE APPLETS

HISTORY OF THE METHODS/FLOW CHART

PUBLICATIONS

EDUCATIONAL MATERIAL

ACKNOWLEDGEMENTS

ABOUT THE AUTHOR/CV

















Copyright:
1996, 1999, 2006
J.A. Sethian

The Narrow Band Level Set Method
You are currently in the
topic outlined in red. 		Overview of and references for papers on theory Overview of and references for papers on link to hyperbolic equations Overview of and references for level_set methods Overview of and references for on stationary formulation Overview of and references for Narrow Band formulation Overview of and references for papers on Fast Marching Methods Work on unstructured mesh versions of level set and fast marching methods Coupling interface methods to complex physics Adaptive mesh refinement Applications to semiconductor modeling Applications to geometry Applications to medical imaging Applications to constructing geodesics on surfaces Applications to seismology and travel times Applications to combustion Applications to fluid mechanics Applications to materials sciences Applications to robotics Applications to computer graphics Applications to CAD/CAM Applications to mesh generation

Click on navigable flow chart to go to new topic

click on any text
to go to a new topic.


The central idea of level set methods is to track a propagating interface by embedding it as the zero level set of a higher-dimensional function. This implicit representation allows one to track changes in topology, and allows one to calculate geometric quantities such as the normal direction and the curvature by capitalizing on the smoothness of the level set function in a neighborhood of th zero level set of interest. However, this embedding comes at a substantial price; one is now tracking all the level sets, not just the one of interest.

The Narrow Band Level Set Method, introduced in Ref. 1 below, solves this problem by focusing computational energy in a thin band around the front itself. Using this approach, the operation count for the level set method drops from O(N*N) in two dimensions to O(k N), where N is the number of points in each space dimension and k is the width of the narrow band. Ref. 2 is an earlier use of this technique.

This savings is substantial; it allows three-dimensional interface evolution problems to be handled with ease.


New Book and Resource on Level Set and Fast Marching Methods



References:

  1. A Fast Level Set Method for Propagating Interfaces : Adalsteinsson, D., and Sethian, J.A., Journal Computational Physics, 118, 2, pp. 269-277, 1995.
    Abstract

    A method is introduced to decrease the computational labor of the standard level set method for propagating interfaces. The fast approach uses only points close to the curve at every time step. We describe this new algorithm and compare its efficiency and accuracy with the standard level set approach.

    Download publications

  2. Computing Minimal Surfaces via Level Set Curvature Flow : Chopp, D.L. Journal of Computational Physics, 106, pp. 77-91, 1993.

    Download publications