Some improvements of the fast marching method

David L Chopp*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

174 Scopus citations

Abstract

The fast marching method published by Sethian [Proc. Natl. Acad. Sci. USA, 93 (1996), pp. 1591-1595] is an optimally efficient algorithm for solving problems of front evolution where the front speed is monotonic. It has been used in a wide variety of applications such as robotic path planning [R. Kimmel and J. Sethian, Fast Marching Methods for Computing Distance Maps and Shortest Paths, Tech. Report 669, CPAM, University of California, Berkeley, 1996], crack propagation [M. Stolarska et al., Internat. J. Numer. Methods Engrg., 51 (2001), pp. 943-960; N. Sukumar, D. L. Chopp, and B. Moran, Extended finite element method and fast marching method for three-dimensional fatigue crack propagation, J. Comput. Phys., submitted], seismology [J. Serbian and A. Popovici, Geophysics, 64 (1999), pp. 516-523], photolithography [J. Sethian, Fast marching level set methods for three-dimensional photolithography development, in Proceedings of the SPIE 1996 International Symposium on Microlithography, Santa Clara, CA, 1996], and medical imaging [R. Malladi and J. Serbian, Proc. Natl. Acad. Sci. USA, 93 (1996), pp. 9389-9392]. It has also been a valuable tool for the implementation of modern level set methods where it is used to efficiently compute the distance to the front and/or an extended velocity function. In this paper, we improve upon the second order fast marching method of Sethian [SIAM Rev., 41 (1999), pp. 199-235] by constructing a second order approximation of the interface generated from local data on the mesh. The data is interpolated on a single box of the mesh using a bicubic approximation. The distance to the front is then calculated by using a variant of Newton's method to solve both the level curve equation and the orthogonality condition for the nearest point to a given node. The result is a second order approximation of the distance to the interface which can then be used to produce second order accurate initial conditions for the fast marching method and a third order fast marching method.

Original languageEnglish (US)
Pages (from-to)230-244
Number of pages15
JournalSIAM Journal on Scientific Computing
Volume23
Issue number1
DOIs
StatePublished - Apr 16 2002

Keywords

  • Bicubic interpolation
  • Fast marching method
  • Level set method
  • Reinitialization

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Some improvements of the fast marching method'. Together they form a unique fingerprint.

Cite this