Summary: The fast marching method published by J. A. Sethian [Proc. Natl. Acad. Sci. USA 93, No. 4, 1591-1595 (1996; Zbl 0852.65055)] 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, D. L. Chopp, N. Moës, and T. Bolytschko, Int. J. Numer. Methods Eng. 51, No. 8, 943-960 (2001; Zbl 1022.74049); 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. Sethian and A. Popovici, Geophysics 64, 516-523 (1999)], 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. Sethian, Proc. Natl. Acad. Sci. USA 93, No. 18, 9389-9392 (1996; Zbl 0858.65150)]. 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 J. A. Sethian [SIAM Rev. 41, No. 2, 199-235 (1999; Zbl 0926.65106)] 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.