Level set method: Information from Answers.com

The level set method (sometimes abbreviated as LSM) is a numerical technique for tracking interfaces and shapes. The advantage of the level set method is that one can perform numerical computations involving curves and surfaces on a fixed Cartesian grid without having to parameterize these objects (this is called the Eulerian approach).^[1] Also, the level set method makes it very easy to follow shapes that change topology, for example when a shape splits in two, develops holes, or the reverse of these operations. All these make the level set method a great tool for modeling time-varying objects, like inflation of an airbag, or a drop of oil floating in water.

1 Level set method
2 The level set equation
3 History
4 See also
5 References
6 External links

Level set method

An illustration of the level set method

A very simple, yet powerful way to understand the level set method is by first studying the accompanying illustration before proceeding towards a more technical definition, which then becomes quite accessible. The figure on the right illustrates several important ideas about the level set method. In the upper-left corner we see a shape; that is, a bounded region with a well-behaved boundary. Below it, the red surface is the graph of a level set function $\varphi$ determining this shape, and the flat blue region represents the $x - y$ plane. The boundary of the shape is then the zero level set of $\varphi$ , while the shape itself is the set of points in the plane for which $\varphi$ is positive (interior of the shape) or zero (at the boundary).

In the top row we see the shape changing its topology by splitting in two. It would be quite hard to describe this transformation numerically by parameterizing the boundary of the shape and following its evolution. One would need an algorithm able to detect the moment the shape splits in two, and then construct parameterizations for the two newly obtained curves. On the other hand, if we look at the bottom row, we see that the level set function merely got translated downward. We see that it is much easier to work with a shape through its level set function than with the shape directly, where we would need to watch out for all the possible deformations the shape might undergo.

Thus, in two dimensions, the level set method amounts to representing a closed curve $Γ$ (such as the shape in our example) using an auxiliary function $\varphi$ , called the level set function. $Γ$ is represented as the zero level set of $\varphi$ by

$\Gamma = \{(x, y)|\, \varphi(x, y) = 0 \}, \,$

and the level set method manipulates $Γ$ implicitly, through the function $\varphi$ . $\varphi$ is assumed to take positive values inside the region delimited by the curve $Γ$ and negative values outside.^[2]^[3]

The level set equation

If the curve $Γ$ moves in the normal direction with a speed v, then the level set function $\varphi$ satisfies the level set equation

$\frac{\partial\varphi}{\partial t} = v|\nabla \varphi|.$

Here, $|\cdot|$ is the Euclidean norm (denoted customarily by single bars in PDEs), and $t$ is time. This is a partial differential equation, in particular a Hamilton-Jacobi equation, and can be solved numerically, for example by using finite differences on a Cartesian grid. ^[2]^[3]

The numerical solution of the level set equation, however, requires sophisticated techniques. Simple finite difference methods fail quickly. Upwinding methods, such as the Godunov method, fare better; however the level set method does not guarantee the conservation of the volume and the shape of the level set in an advection field that does conserve the shape and size, for example uniform or rotational velocity field. Instead, the shape of the level set may get severely distorted and the level set may vanish over several time steps. For this reason, high-order finite difference schemes are generally required, such as high-order essentially non-oscillatory (ENO) schemes, and even then, the feasibility of long-time simulations is questionable. Further sophisticated methods to deal with this difficulty have been developed, e.g., combinations of the level set method with tracing marker particles advected by the velocity field.^[4]

History

The level set method was developed in the 1980s by the American mathematicians Stanley Osher and James Sethian. It has become popular in many disciplines, such as image processing, computer graphics, computational geometry, optimization, and computational fluid dynamics.

A number of level set data structures have been developed to facilitate the use of the level set method in computer applications.

References

^ Osher, S. & J. A. Sethian (1988), "Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations", J. Comput. Phys. 79: 12–49.
^ ^a ^b Osher, Stanley J.; Fedkiw, Ronald P. (2002). Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag. ISBN 0-387-95482-1.
^ ^a ^b Sethian, James A. (1999). Level Set Methods and Fast Marching Methods : Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press. ISBN 0-521-64557-3.
^ Enright, D.; R. P. Fedkiw & J. H. Ferziger et al. (2002), "A hybrid particle level set method for improved interface capturing", J. Comput. Phys. 183: 83–116.

External links

See Ronald Fedkiw's academic web page for many stunning pictures and animations showing how the level set method can be used to model real life phenomena, like fire, water, cloth, fracturing materials, etc.
Multivac is a C++ library for front tracking in 2D with level set methods.
James Sethian's web page on level set method.
Stanley Osher's homepage.

v • d • e Numerical partial differential equations

Finite difference methods	Heat Equation and related: FTCS scheme · Crank–Nicolson method Hyperbolic: Lax–Friedrichs method · Lax–Wendroff method · MacCormack method · Upwind scheme · Other: Alternating direction implicit method · Finite-difference time-domain method

Finite volume methods	Godunov's scheme · High-resolution scheme · MUSCL scheme · AUSM · Riemann solver

Finite element methods	hp-FEM · Extended finite element method · Discontinuous Galerkin method · Spectral element method · Meshfree methods · Mortar methods

Other methods	Spectral method · Pseudospectral method · Method of lines · Multigrid methods · Collocation method · Level set method · Boundary element method · Analytic element method · Particle-in-cell

Domain decomposition methods	Schur complement method · Fictitious domain method · Schwarz alternating method · Additive Schwarz method · Abstract additive Schwarz method · Neumann–Dirichlet method · Neumann–Neumann methods · Poincaré–Steklov operator · Balancing domain decomposition · BDDC · FETI · FETI-DP

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	Level set (data structures)
	Signed distance function
	List of numerical computational geometry topics

	What level should your fridge be set at? Read answer...
	Calculation of reduced level in rise and fall method? Read answer...
	What is the calculation for the calibration of a Level instrument displacement type dry method? Read answer...

	What is 3-list method of setting priorities?
	Methods of describing a set?
	What are the methods of naming sets of operations?

Level set method

Contents

Level set method

The level set equation

History

See also

References

External links