A convergent monotone difference scheme for motion of level sets by mean curvature. (English) Zbl 1070.65082

There has been a great deal of interest in motion by mean curvature, in terms of both theory and computation. The equation for motion of level sets by mean curvature (MC) in \(\mathbb{R}^n \) is given by \[ u_t = \Delta _1 u \equiv |Du|\text{ div}\left(\frac{Du}{|Du|}\right) \equiv \sum_{i = 1}^n {u_{x_i x_i }} - \frac{1}{|Du|^2} \sum_{i,j = 1}^n {u_{x_i x_j} u_{x_i} u_{x_j}}. \] This equation arises from the well-known level set method, which gives the normal velocity, \(v_n\), of the level set of the function \(u(x)\) as \(v_n = \frac{u_t}{|Du|}\). The unit normal of the level set is given by the direction of the gradient, \(\frac{Du}{|Du|}\), and the mean curvature is the divergence of the unit normal, resulting in (MC). The level set method has been successful both as a framework for the theoretical study and as a numerical method for the simulation of the motion.
Applications of motion by mean curvature, and of related geometric motions, can be found in many areas, including differential geometry, fluid dynamics, combustion, front propagation and image processing. Despite the great deal of interest, no practical, provably convergent numerical scheme has been proposed for the equation for motion of level sets by mean curvature.
An obvious approach to building a difference scheme for (MC) is to simply combine centered finite differences for each of the terms in the equation. The author presents a numerical experiment which demonstrates that this approach is not convergent.
An explicit convergent finite difference scheme for motion of level sets by mean curvature is presented in the paper. The scheme is defined on a Cartesian grid, using neighbors arranged approximately in a circle. The accuracy of the scheme, which depends on the radius of the circle, \(dx\), and on the angular resolution, \(d\theta \), is formally \(O(dx^2 + d\theta)\). The scheme is explicit and nonlinear: the update involves computing the median of the values at the neighboring grid points.
In the first section of the paper the simplest version of the scheme is presented. Despite its limited accuracy, this version of the scheme may be of practical use. A possibility is in applications to image processing, where the data itself has a natural discrete structure. This version of scheme is presented with an arbitrary spatial resolution, but with a nine point stencil. The scheme is monotone: increasing any of the neighboring values will lead to an increase (or no change) in the value of the solution.
In the second section it is shown that the scheme can be implemented in general (structured, unstructured) geometries, in two or more dimensions. For concreteness, the author first addresses the scheme on a uniform grid in two dimensions. In this context, a detailed convergence proof is given. The requirements for the choice of neighbors specified so that the scheme may easily be adapted to an unstructured grid. The extension to higher dimensions is men addressed.
A numerical consistency is checked in the third section. This is followed by testing the accuracy of the numerical solution against an exact solution, using different stencils and grid sizes. Finally, an example which demonstrates the fattening phenomena is presented.


65M12 Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs
65M06 Finite difference methods for initial value and initial-boundary value problems involving PDEs
35K55 Nonlinear parabolic equations
35J70 Degenerate elliptic equations
35K65 Degenerate parabolic equations
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
Full Text: DOI


[1] Barles, G., Georgelin, C.: A simple proof of convergence for an approximation scheme for computing motions by mean curvature. SIAM J. Numer. Anal. 32(2), 484-500 (1995) · Zbl 0831.65138
[2] Barles, G., Souganidis, P.E.: Convergence of approximation schemes for fully nonlinear second order equations. Asymptotic Anal. 4(3), 271-283 (1991) · Zbl 0729.65077
[3] Chen, Y.G., Giga, Y., Goto, S.: Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations. J. Differential Geom. 33(3), 749-786 (1991) · Zbl 0696.35087
[4] Crandall, M.G., Ishii, H., Lions, P.-L.: User?s guide to viscosity solutions of second order partial differential equations. Bull. Amer. Math. Soc. (N.S.) 27(1), 1-67 (1992) · Zbl 0755.35015
[5] Crandall, M.G. Lions, P.-L.: Convergent difference schemes for nonlinear parabolic equations and mean curvature motion. Numer. Math. 75(1), 17-41 (1996) · Zbl 0874.65066
[6] Michael G. Crandall. Viscosity solutions: a primer. In: Viscosity solutions and applications (Montecatini Terme, 1995), Springer, Berlin, 1997, pp. 1-43 · Zbl 0901.49026
[7] Evans, L.C., Spruck, J.: Motion of level sets by mean curvature. I. J. Diff. Geom. 33(3), 635-681 (1991) · Zbl 0726.53029
[8] Evans, L.C., Soner, H.M., Souganidis, P.E.: Phase transitions and generalized motion by mean curvature. Comm. Pure Appl. Math. 45(9), 1097-1123 (1992) · Zbl 0801.35045
[9] Evans, L.C.: Partial differential equations. American Mathematical Society, Providence, RI, 1998 · Zbl 0902.35002
[10] Merriman, B., Bence, J.K., Osher, S.J.: Motion of multiple functions: a level set approach. J. Comput. Phys. 112(2), 334-363 (1994) · Zbl 0805.65090
[11] Motzkin, T.S., Wasow, W.: On the approximation of linear elliptic differential equations by difference equations with positive coefficients. J. Math. Physics 31, 253-259 (1953) · Zbl 0050.12501
[12] Oberman, A.M.: Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton-Jacobi equations and free boundary problems. SINUM, To appear 2005 · Zbl 1124.65103
[13] Osher, S., Fedkiw, R.: Level set methods and dynamic implicit surfaces. volume 153 of Appl. Math. Sci. Springer-Verlag, New York, 2003 · Zbl 1026.76001
[14] Osher, S., Paragios, N.: (eds.), Geometric level set methods in imaging, vision, and graphics. Springer-Verlag, New York, 2003 · Zbl 1027.68137
[15] Osher, S., Sethian, J.A.: Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys. 79(1), 12-49 (1988) · Zbl 0659.65132
[16] Sethian, J.A.: Level set methods and fast marching methods. volume 3 of Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge, second edition, 1999. Evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science. · Zbl 0973.76003
[17] Walkington, N.J.: Algorithms for computing motion by mean curvature. SIAM J. Numer. Anal. 33(6), 2215-2238 (1996) · Zbl 0863.65061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.