Fast semi-Lagrangian schemes for the eikonal equation and applications

We introduce and analyze a fast version of the semi-Lagrangian algorithm for front propagation originally proposed in [M. Falcone, "The minimum time problem and its applications to front propagation," in Motion by Mean Curvature and Related Topics, A. Visintin and G. Buttazzo, eds., de Gruyter, Berlin, 1994, pp. 70-88]. The new algorithm is obtained using the local definition of the approximate solution typical of semi-Lagrangian schemes and redefining the set of "neighboring nodes" necessary for fast marching schemes. A new proof of convergence is needed since that definition produces a new narrow band centered at the interphase which is larger than the one used in fast marching methods based on finite differences. We show that the new algorithm converges to the viscosity solution of the problem and that its complexity is O(N log N(nb)), as it is for the fast marching method based on. finite difference (N and N(nb) being, respectively, the total number of nodes and the number of nodes in the narrow band). A new sufficient condition for the convergence of the standard. finite difference fast marching method is also given. We present several tests comparing the two algorithms and other fast methods (e.g., fast sweeping) on a series of benchmarks which include the minimum time problem and the shape-from-shading problem.