Some improvements of the fast marching method

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 volution where the front speed is monotonic. It has been used in a wide variety of applications such as robotic path planning [R. K immel 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. Method s Engrg., 51 ( 2001), pp. 943-960; N. Sukumar, D. L. Chopp, and B. Moran, E xtended finite element method and fast marching method for three-dimensiona l fatigue crack propagation, J. Comput. Phys., submitted], seismology [ J. Sethian and A. Popovici, Geophysics, 64 (1999), pp. 516-523], photolithogra phy [ J. Sethian, Fast marching level set methods for three-dimensional pho tolithography development, in Proceedings of the SPIE 1996 International Sy mposium on Microlithography, Santa Clara, CA, 1996], and medical imaging [ R. Malladi and J. Sethian, Proc. Natl. Acad. Sci. USA, 93 ( 1996), pp. 9389 -9392]. It has also been a valuable tool for the implementation of modern l evel set methods where it is used to efficiently compute the distance to th e front and/or an extended velocity function. In this paper, we improve upon the second order fast marching method of Set hian [SIAM Rev., 41 ( 1999), pp. 199-235] by constructing a second order ap proximation of the interface generated from local data on the mesh. The dat a 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 condi tion for the nearest point to a given node. The result is a second order ap proximation of the distance to the interface which can then be used to prod uce second order accurate initial conditions for the fast marching method a nd a third order fast marching method.