Legendre-transform-based fast sweeping methods for static Hamilton-Jacobi equations on triangulated meshes

We propose a new sweeping algorithm which utilizes the Legendre transform of the Hamiltonian on triangulated meshes. The algorithm is a general extension of the previous proposed algorithm by Kao et al. [CY. Kao, S.J. Osher, Y.-H. Tsai, Fast sweeping method for static Hamilton-Jacobi equations, SIAM J. Numer. Anal. 42 (2005) 2612-2632]. The algorithm yields the numerical solution at a grid point using only its one-ring neighboring grid values and is easy to implement numerically. The minimization that is related to the Legendre transform in the sweeping algorithm can either be solved analytically or numerically. The scheme is shown to be monotone and consistent. We illustrate the efficiency and accuracy of the new method with several numerical examples in two and three dimensions. (C) 2008 Elsevier Inc. All rights reserved.