A PDE-based fast local level set method. (English) Zbl 0964.76069

From the summary: We develop a fast method to localize the level set method of S. Osher and J. A. Sethian [ibid. 79, No. 1, 12-49 (1988; Zbl 0659.65132)], and address two important issues that are intrinsic to the level set method: (a) how to extend a quantity that is given only on the interface to a neighborhood of the interface; (b) how to reset the level set function to be a signed distance function to the interface efficiently without appreciably moving the interface. This fast local level set method reduces the computational effort by one order of magnitude, works in as much generality as the original one, and is conceptually simple and easy to implement.
Our approach differs from previous related works in that we extract all the information needed from the level set function (or functions in multiphase flow) and do not need to find explicitly the location of the interface in the space domain. The complexity of our method to do tasks such as extension and distance reinitialization is \(O(N)\), where \(N\) is the number of points in space, not \(O(N\log N)\). This complexity estimation is also valid for quite general geometrically based front motion for our localized method.


76M25 Other numerical methods (fluid mechanics) (MSC2010)


Zbl 0659.65132
Full Text: DOI Link


[1] Adalsteinsson, D.; Sethian, J.A., A fast level set method for propagating interfaces, J. comput. phys., 118, 269, (1995) · Zbl 0823.65137
[2] Adalsteinsson, D.; Sethian, J.A., The fast construction of extension velocities in level set methods, J. comput. phys., 148, 2, (1999) · Zbl 0919.65074
[3] Bardi, M.; Osher, S., The nonconvex multi-dimensional Riemann problem for hamilton – jacobi equations, J. numer. anal., 22, 344, (1991) · Zbl 0733.35073
[4] Chen, Y.G.; Giga, Y.; Goto, S., Uniqueness and existence of viscosity solutions of generalized Mean curvature flow equations, J. diff. geom., 33, 749, (1991) · Zbl 0696.35087
[5] Chang, Y.C.; Hou, T.Y.; Merriman, B.; Osher, S., A level set formulation of Eulerian interface capturing methods for incompressible fluid flows, J. comput. phys., 124, 449, (1996) · Zbl 0847.76048
[6] Chopp, D.L.; Sethian, J.A., Flow under curvature: singularity formulation, minimal surfaces, and geodesics, J. exper. math., 2, 235, (1993) · Zbl 0806.53004
[7] Chen, S.; Merriman, B.; Osher, S.; Smereka, P., A simple level set method for solving Stefan problems, J. comput. phys., 135, 8, (1995) · Zbl 0889.65133
[8] Evans, L.C.; Spruck, J., Motion of level set via Mean curvature I, J. diff. geom., 33, 635, (1991) · Zbl 0726.53029
[9] Hou, T.; Li, Z.; Osher, S.; Zhao, H.K., A hybrid method for moving interface problems with applications to the Hele-Shaw flows, J. comput. phys., 134, (1997)
[10] Harabetian, E.; Osher, S., Regularization of ill-posed problems via the level set approach, Siap, 58, 1689, (1998) · Zbl 0914.65098
[11] Harabetian, E.; Osher, S.; Shu, C.W., An Eulerian approach for vortex motion using a level set regularization procedure, J. comput. phys., 127, 15, (1996) · Zbl 0859.76052
[12] J. Helmsen, E. G. Puckett, P. Colella, and, M. Dorr, Two new methods for simulating photolithography development in 3D, in, SPIE Microlithography IX, 1996, p, 253.
[13] Jiang, G.S.; Peng, D., SIAM J. sci. comput., (1997)
[14] M. Kang, B. Merriman, S. Osher, and, P. Smereka, A Level Set Approach for the Motion of Soap Bubbles with Curvature Dependent Velocity or Acceleration, UCLA CAM report 96-19.
[15] Merriman, B.; Bence, J.; Osher, S., Motion of multiple junctions: A level set approach, J. comput. phys., 112, 334, (1994)
[16] B. Merriman, R. Caflisch, and, S. Osher, Level set methods with application to island dynamics, in, Proceedings of Meeting on Free Boundary Problems: Theory and Application, Crete, 1997, edited by, I. Athasopoulos, G. Markrikis, and J. F. Rodrigues, CRC Press, Boca Raton, FL, 1999. [UCLA CAM Report 98-10.]
[17] Mulder, W.; Osher, S.; Sethian, J.A., Computing interface motion in compressible gas dynamics, J. comput. phys., 100, 209, (1992) · Zbl 0758.76044
[18] S. Osher, Subscale capturing in numerical analysis, in, Proceeding of the International Congress of Mathematicians, Zurich, 1994, Birkhauser, Basel, p, 1449. · Zbl 0839.65093
[19] Osher, S., A level set formulation for the solution of the Dirichlet problem for Hamilton-Jacobi equations, SIAM J. numer. anal., 24, 1145, (1993) · Zbl 0804.35021
[20] Osher, S.; Sethian, J.A., Fronts propagating with curvature dependent speed: algorithms based on Hamilton-Jacobi formulation, J. comput. phys., 79, 12, (1988) · Zbl 0659.65132
[21] Osher, S.; Shu, C.W., High-order essentially non-oscillatory schemes for Hamilton-Jacobi equations, J. numer. anal., 28, 907, (1991) · Zbl 0736.65066
[22] Sethian, J.A., Level set methods: evolving interfaces in geometry, fluid mechanics, computer vision, and material science, (1996) · Zbl 0859.76004
[23] Sethian, J.A., A fast marching level set method for monotonically advancing fronts, Proc. nat. acad. sci., 93, 1591, (1996) · Zbl 0852.65055
[24] Shu, C-W., Total-variation-diminishing time discretization, SIAM J. sci. stat. comput., 9, 1073, (1988) · Zbl 0662.65081
[25] Shu, C.W.; Osher, S., Efficient implementation of essentially nonoscillatory shock capturing schemes, J. comput. phys., 77, 439, (1988) · Zbl 0653.65072
[26] Sussman, M.; Smereka, P.; Osher, S., A level set method for computing solutions to incompressible two-phase flow, J. comput. phys., 119, 146, (1994) · Zbl 0808.76077
[27] Zhao, H.K.; Chan, T.; Merriman, B.; Osher, S., A variational level set approach to multi-phase motion, J. comput. phys., 122, 179, (1996) · Zbl 0860.65050
[28] Zhao, H.K.; Merriman, B.; Osher, S.; Wang, L., Capturing the behavior of bubbles and drops using the variational level set approach, J. comput. phys., 143, 495, (1998) · Zbl 0936.76065
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.