• Technical Publications
  • Books
  • Popular Articles




    1996, 1999, 2006
    J.A. Sethian

    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


    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

    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