×

Local level set method in high dimension and codimension. (English) Zbl 1086.65088

Summary: A new method is presented for numerically capturing a moving interface of arbitrary dimension and codimension. The method is named the ‘local level set method’, since it localizes the level set method near the interface to significantly reduce the computational expense of the level set method. Following the framework of the level set method, an interface is implicitly represented as the zero level set of a vector valued function. A spatial tree structure is used to locally sample the vector valued function near the interface. Using a Lipschitz stable interpolation and a semi-Lagrangian scheme, our method is stable under both the maximum norm and the Lipschitz semi-norm. Due to this stability, the method does not need to reinitialize a level set function. Several numerical examples with high codimension are successfully tested.

MSC:

65M06 Finite difference methods for initial value and initial-boundary value problems involving PDEs
35L45 Initial value problems for first-order hyperbolic systems
35L60 First-order nonlinear hyperbolic equations
65M55 Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs
65M50 Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs
65M12 Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Harten, A.; Engquist, B.; Osher, S.; Chakravarthy, S., Uniformly high-order accurate essentially non-oscillatory schemes III, J. Comput. Phys, 71, 231-303 (1987) · Zbl 0652.65067
[2] Min, C., Simplicial isosurfacing in arbitrary dimension and codimension, J. Comput. Phys, 190, 295-310 (2003) · Zbl 1029.65016
[3] Lee, C. W., Subdivisions and triangulations of polytopes, Handbook of Discrete and Computational Geometry (1997), CRC Press LLC · Zbl 0917.52012
[4] Adalsteinsson, D.; Sethian, J., A fast level set method for propagating interfaces, J. Comput. Phys, 118, 269-277 (1995) · Zbl 0823.65137
[5] Peng, D.; Merriman, B.; Zhao, H.; Osher, S.; Kang, M., A PDE based fast local level set method, J. Comput. Phys, 155, 410-438 (1999) · Zbl 0964.76069
[6] H.K. Zhao, S. Osher, R. Fedkiw, Fast surface reconstruction using the level set method, in: 1st IEEE Workshop on Variational and Level Set Methods, 8th ICCV, Vancouver, 2001, pp. 194-202; H.K. Zhao, S. Osher, R. Fedkiw, Fast surface reconstruction using the level set method, in: 1st IEEE Workshop on Variational and Level Set Methods, 8th ICCV, Vancouver, 2001, pp. 194-202
[7] Zhao, H. K.; Osher, S.; Merriman, B.; Kang, M., Implicit and nonparametric shape reconstruction from unorganized data using a variational level set method, Comput. Vis. Image Understand, 80, 295-314 (2000) · Zbl 1011.68538
[8] Samet, H., The design and analysis of spatial data structures (1990), Addison-Wesley
[9] Samet, H., Applications of spatial data structures: computer graphics, image processing and GIS (1990), Addison-Wesley
[10] Strain, J., Fast tree based redistancing for level set computations, J. Comput. Phys, 152, 648-666 (1999) · Zbl 0944.65020
[11] Strain, J., Tree methods for moving interfaces, J. Comput. Phys, 151, 616-648 (1999) · Zbl 0942.76061
[12] Ambrosio, L.; Soner, M., Level set approach to mean curvature flow in arbitrary codimension, J. Diff. Geom, 43, 693-737 (1996) · Zbl 0868.35046
[13] L. Lorigo, O. Faugeras, W. Grimson, R. Keriven, R. Kikinis, A. Nabavi, C. Westin, Codimension-two geodesic active contours for the segmentation of tubular structures, in: Conference on Computer Vision and Pattern Recognition, IEEE 2000, pp. 444-451; L. Lorigo, O. Faugeras, W. Grimson, R. Keriven, R. Kikinis, A. Nabavi, C. Westin, Codimension-two geodesic active contours for the segmentation of tubular structures, in: Conference on Computer Vision and Pattern Recognition, IEEE 2000, pp. 444-451
[14] Rudin, L.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Physica D, 60, 259-268 (1992) · Zbl 0780.49028
[15] M. Droske, B. Meyer, M. Rumpf, C. Schaller, An adaptive level set method for medical image segmentation, Lecture Notes in Computer Science IPMI (2001) 416-422; M. Droske, B. Meyer, M. Rumpf, C. Schaller, An adaptive level set method for medical image segmentation, Lecture Notes in Computer Science IPMI (2001) 416-422 · Zbl 0982.68546
[16] Bayer, M. M.; Barycentric subdivisions, Pacific J. Math, 135, 1-16 (1988) · Zbl 0627.57020
[17] Sussman, M.; Smereka, P.; Osher, S., A level set approach to computing solutions to incompressible two-phase flow, J. Compt. Phys, 114, 146-159 (1994) · Zbl 0808.76077
[18] Butchard, P.; Cheng, L.-T.; Merriman, B.; Osher, S., Motion of curves in three spatial dimensions using a level set approach, J. Comput. Phys, 170, 720-741 (1999)
[19] Fedkiw, R.; Aslam, T.; Xu, S., The ghost fluid method for deflagration and detonation discontinuities, J. Compt. Phys, 154, 393-427 (1999) · Zbl 0955.76071
[20] Osher, S.; Sethian, J., Fronts propagating with curvature dependent speed: algorithms based on hamilton-jacobi formulations, J. Comput. Phys, 79, 12-49 (1988) · Zbl 0659.65132
[21] Osher, S.; Cheng, L.-T.; Kang, M.; Shim, H.; Tsai, Y.-H., Geometric optics in a phase space based level set and eulerian framework, J. Comput. Phys, 179, 622-648 (2002) · Zbl 0999.78002
[22] Chan, T.; Vese, L., Active contours without edges, IEEE Trans. Image Process, 10, 266-277 (2001) · Zbl 1039.68779
[23] Liu, X.-D.; Osher, S.; Chan, T., Weighted essentially non-oscillatory schemes, J. Comput. Phys, 126, 202-212 (1996)
[24] Y.-H. Tsai, L.-T. Cheng, S. Osher, P. Burchard, G. Sapiro, Visibility and its dynamics in a PDE based implicit framework, UCLA CAM Report 03-22; Y.-H. Tsai, L.-T. Cheng, S. Osher, P. Burchard, G. Sapiro, Visibility and its dynamics in a PDE based implicit framework, UCLA CAM Report 03-22 · Zbl 1056.65018
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.