Level Set Methods and Fast Marching Methods
Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science

J.A. Sethian, Cambridge University Press, 1999
Cambridge Monograph on Applied and Computational Mathematics

Overview

This is a new book on level set methods and Fast Marching Methods, which are numerical techniques for analyzing and computing interface motion in a host of settings. The numerical techniques can be used to track three-dimensional complex fronts that can develop sharp corners and change topology as they evolve. The text includes applications from physics, chemistry, fluid mechanics, combustion, image processing, material science, seismology, fabrication of microelectronic components, computer vision and control theory. The book is intended for mathematicians, applied scientists, practicing engineers, computer graphic artists, and anyone interested in the evolution of boundaries and interfaces.

The book is written on an introductory level. As a prerequisite, it is suggested that the reader be acquainted with some beginning programming, vector calculus, and some very basic aspects of scientific computing. The text is an equal blend of theory, implementations, and applications areas, including detailed descriptions of the appropriate numerical schemes.

Comparison with previous edition

This new book, available in both hardback and paperback, is a superset of the previous edition, entitled Level Set Methods. That is, it includes everything in the previous book, plus a large collection of new topics, including work on

Triangulated Level set Methods and Fast Marching Methods
Higher order Fast Marching Methods
Extension velocities: Coupling Interface Methods to Arbitrary Physics
General Methodology for Assembling Level Set Methods
Constructing Level Set Methods which Conserve Mass
Avoiding all reinitialization algorithms
Error Analysis of Various Schemes
Sintering, Surface Diffusion and Flow under Second Derivative of Curvature
Shape Smoothing
Fast Techniques for Computing Visibility
Semi-Conductors/Comparison with experiment
Fast Marching Methods for Seismic travel times and pre-stack migration
Voronoi Diagrams, Shape Offsetting
Shortest Paths on Manifolds
Continuous vs. Discrete Network Path Algorithms
Connection to aircraft avoidance
Electromigration of Voids and Metallization Failures

Download the First Chapter

The first chapter of this new book may be downloaded:

Compressed Postscript
Uncompressed Postscript
Compressed PDF
Uncompressed PDF

Availability, Links, and Ordering from Cambridge University Press:

Both hardback and paperback versions of the book are available in May, 1999.

North America
Everywhere else

Table of Contents of New Edition

Preface to the Second Edition
Introduction
Part I: Equations of Motion for Moving Interfaces
1. Formulation of Interface Propagation
  1. A boundary value formulation
  2. An initial value formulation
  3. Advantages of these perspectives
  4. A general framework
  5. A look ahead/A look back
  6. A larger perspective
Part II: Theory and Algorithms
1. Theory of Curve and Surface Evolution
  1. Fundamental formulation
  2. Total variation: stability and the growth of oscillations
  3. The role of entropy conditions and weak solutions
  4. Effects of curvature
2. Viscosity Solutions and Hamilton--Jacobi Equations
  1. Viscosity solutions of Hamilton--Jacobi equations
  2. Some additional comments and references
3. Traditional Techniques for Tracking Interfaces
  1. Marker/string methods
  2. Volume-of-fluid techniques
  3. Constructing an approximation to the gradient
4. Hyperbolic Conservation Laws
  1. First order schemes
    1. Higher order schemes for the linear wave
  2. The non-linear wave equation
    1. Discontinuous solutions and shocks
    2. Weak solutions, flux condition, and approximation schemes
    3. The method of artificial viscosity
    4. Less diffusive schemes: Lax--Friedrichs
    5. Even less diffusive schemes: exact and approximate Riemann solvers
5. Basic Algorithms for Interface Evolution
  1. Convergence of schemes for Hamilton-Jacobi equations
  2. Hyperbolic schemes and Hamilton-Jacobi equations
  3. One-dimensional schemes
  4. Higher-dimensional schemes
  5. The example of a propagating one-dimensional graph
  6. The initial value problem: the Level Set Method
  7. Stability and the CFL condition
  8. Higher order time schemes
  9. The boundary value problem: the stationary method
  10. Schemes for non-convex speed functions
  11. Approximations to geometric variables
  12. Calculating additional quantities
  13. Initialization
  14. Computational domain boundary conditions
  15. Putting it all together
Part III: Efficiency, Adaptivity, and Extensions
1. Efficient Schemes: the Narrow Band Level Set Method
  1. Parallel algorithms
  2. Adaptive mesh refinement
  3. Narrow banding and fast methods
  4. Details of the Narrow Band implementation
2. Efficient Schemes: Fast Marching Methods
  1. Iteration
  2. Causality
  3. The update procedure for the Fast Marching Method}
  4. Heap sorts and computational efficiency
  5. Initial conditions
  6. Network path algorithms
  7. The Link between Dijkstra's method and Huygens' principle
  8. Optimal orderings
  9. Higher accuracy Fast Marching Methods
  10. Accuracy/order of this scheme
  11. Non-uniform orthogonal grids
  12. General static Hamilton--Jacobi equations
  13. Some clarifying comments
3. Triangulated Versions of Level Set Methods
  1. Fundamentals and notation
  2. A monotone scheme for H(\nabla u)
  3. A positive scheme for homogeneous H(\nabla u)
  4. A Petrov-Galerkin formulation
  5. Time integration schemes
  6. Algorithms
    1. The explicit positive coefficient scheme
    2. The explicit Petrov-Galerkin scheme
  7. Schemes for curvature flow
  8. Mesh adaptivity
4. Triangulated Fast Marching Methods
  1. The update procedure
  2. A scheme for a particular triangulated domain
  3. Fast Marching Methods on triangulated domains
    1. A construction for acute triangulations
    2. Extension to general triangulations
5. Constructing Extension Velocities
  1. The need for extension velocities
  2. Various approaches to extension velocities
  3. Equations for extension velocities
  4. Building extension velocities
    1. Constructing signed distances
    2. Constructing the velocity extension
  5. A quick demonstration
  6. Re-initialization
6. Tests of Basic Methods
  1. The basic Cartesian Level Set Method
  2. Triangulated Level Set Methods for H--J equations.
    1. Smooth solutions
    2. Non-smooth solutions
    3. Mesh adaptation and curvature flow
  3. Accuracy of Fast Marching Methods
  4. Tests of extension velocity methodology
    1. Timings
    2. Maintaining the signed distance function
    3. Capturing sub-grid effects
    4. Building Level Set and Fast Marching Applications
Part IV: Applications
1. Geometry
  1. Statement of problem
  2. Equations of motion
  3. Results
  4. Flows under more general metrics
  5. Volume-preserving flows
  6. Motion under the second derivative of curvature
  7. Triple points: variational and diffusion methods
    1. Statement of problem
    2. More complex motions
    3. Diffusion-generation curvature motion
    4. Constraint-based level set flows
2. Grid Generation
  1. Statement of problem
  2. Equations of motion
    1. Construction of body-fitted lines
    2. Construction of transverse lines
    3. Results, complications, and future work
3. Image Enhancement and Noise Removal
  1. Statement of problem
  2. Equations of motion
  3. Curvature-driven noise reduction
  4. The Min/Max flow
    1. Min/Max flow on structures of a prescribed scale
    2. Extension of Min/Max scheme to gray-scale, texture, and color images
    3. Results
  5. Related work
4. Computer Vision: Shape Detection and Recognition
  1. Shape-from-shading
  2. Examples of shape-from-shading
  3. Shape detection/recovery
    1. Thresholding
    2. An expanding interface view
    3. Combining algorithms
  4. Surface evolution and the stereo problem
  5. Reconstruction of obstacles in inverse problems
  6. Shape recognition
    1. Pre-processing recognition for shape reconstruction
    2. Handwritten character recognition
      1. Training the neural network
      2. Perturbing the characters: searching neural net space
5. Combustion, Solidification, Fluids, and Electromigration
  1. Combustion
    1. Vorticity, exothermicity, flame stretch, and wrinkling
    2. Equations of motion
    3. Algorithm and construction of extension velocities
    4. Results
    5. A hybrid scheme for tracking deflagrations
    6. Modeling detonation shock dynamics
  2. Crystal growth and dendritic solidification
    1. Background
    2. Equations of motion
    3. A boundary integral approach
    4. Results
    5. A full grid approach
  3. Fluid mechanics
  4. Additional applications
    1. Groundwater flow
    2. Film boiling
    3. The Marangoni effect
    4. Void evolution and electromigration
      1. Set up and equations of motion
      2. Flow of algorithm
      3. Results
6. Computational Geometry and Computer-aided Design
  1. Shape-Offsetting
  2. Voronoi diagrams
  3. Curve flows with constraints
  4. Minimal surfaces and surfaces of prescribed curvature
    1. Equations of motion/algorithm
    2. Results
    3. Extensions to surfaces of prescribed curvature
  5. Boolean operations on shapes
    1. Boolean operations on implicit functions
    2. A faster algorithm for Boolean shape operations
  6. Extracting and combining two-dimensional shapes
  7. Shape smoothing
7. Optimality and First Arrivals
  1. Optimal path planning
    1. Statement of problem
    2. Results
      1. Two degrees of freedom
      2. Three degrees of freedom
      3. Four Degrees of Freedom
  2. Constructing shortest paths on weighted domains
    1. Shortest paths
    2. Shortest paths with bounces
  3. Constructing shortest paths on manifolds
    1. A flat domain approach
    2. An O(N log N) method for constructing shortest geodesic paths on manifolds
  4. Seismic traveltimes
    1. Background equations
    2. Computing Fast Marching Method traveltimes through a salt structure
    3. Migration using the Fast Marching Method
  5. Aircraft collision avoidance using Level Set Methods
  6. Visibility evaluations
    1. Profile visibility
    2. Visibility around obstacles
8. Etching and Deposition in Microchip Fabrication
  1. Physical effects and background
  2. Equations of motion for etching/deposition
    1. Individual terms
      1. Etching
      2. Deposition
    2. Assembling the terms
      1. Evaluation of the re-emission term
      2. Direct solution of integral equation
      3. Iterative solution of integral equation
    3. Additional numerical issues
      1. Visibility
      2. Extension velocities
      3. Surface diffusion
  3. Two-dimensional results
    1. Etching/deposition
    2. Masking
    3. Ion milling: non-convex sputter laws
    4. Discontinuous etch rates
    5. Test cases: re-emission/re-deposition simulations
    6. Parameter studies of etching and deposition
    7. Trench depth on re-emission profiles
    8. Multiple effects
    9. Thin films and nanolayers
    10. Surface diffusion
  4. Three-dimensional simulations
    1. Photolithography development
    2. Etching and deposition
  5. Complex simulations
  6. Timings
  7. Validation with experimental results
    1. Ion milling
    2. Plasma-enhanced chemical vapor deposition
    3. Spin-on-glass
    4. SRAM simulations
9. Summary/New Areas/Future Work
10. Bibliography
11. Index
Return to Fast Marching/Level Set Main Page

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

Level Set Methods and Fast Marching Methods Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science

J.A. Sethian, Cambridge University Press, 1999 Cambridge Monograph on Applied and Computational Mathematics