A fast sweeping method for Eikonal equations
Author:
Hongkai Zhao
Journal:
Math. Comp. 74 (2005), 603627
MSC (2000):
Primary 65N06, 65N12, 65N15, 35L60
Published electronically:
May 21, 2004
MathSciNet review:
2114640
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In this paper a fast sweeping method for computing the numerical solution of Eikonal equations on a rectangular grid is presented. The method is an iterative method which uses upwind difference for discretization and uses GaussSeidel iterations with alternating sweeping ordering to solve the discretized system. The crucial idea is that each sweeping ordering follows a family of characteristics of the corresponding Eikonal equation in a certain direction simultaneously. The method has an optimal complexity of for grid points and is extremely simple to implement in any number of dimensions. Monotonicity and stability properties of the fast sweeping algorithm are proven. Convergence and error estimates of the algorithm for computing the distance function is studied in detail. It is shown that GaussSeidel iterations is enough for the distance function in dimensions. An estimation of the number of iterations for general Eikonal equations is also studied. Numerical examples are used to verify the analysis.
 1.
Martino
Bardi and Stanley
Osher, The nonconvex multidimensional Riemann problem for
HamiltonJacobi equations, SIAM J. Math. Anal. 22
(1991), no. 2, 344–351. MR 1084960
(91k:35056), http://dx.doi.org/10.1137/0522022
 2.
Michelle
Boué and Paul
Dupuis, Markov chain approximations for deterministic control
problems with affine dynamics and quadratic cost in the control, SIAM
J. Numer. Anal. 36 (1999), no. 3, 667–695. MR 1681057
(2000a:49054), http://dx.doi.org/10.1137/S0036142997323521
 3.
B. Cockburn and J. Qian, A short introduction to continuous dependence results for HamiltonJacobi equations, Collected Lectures on the Preservation of Stability Under Discretization (D. Estep and S. Tavener, Eds.), SIAM, 2002.
 4.
Michael
G. Crandall and PierreLouis
Lions, Viscosity solutions of HamiltonJacobi
equations, Trans. Amer. Math. Soc.
277 (1983), no. 1,
1–42. MR
690039 (85g:35029), http://dx.doi.org/10.1090/S00029947198306900398
 5.
M.
G. Crandall and P.L.
Lions, Two approximations of solutions of
HamiltonJacobi equations, Math. Comp.
43 (1984), no. 167, 1–19. MR 744921
(86j:65121), http://dx.doi.org/10.1090/S00255718198407449218
 6.
P. Danielsson, Euclidean distance mapping, Computer Graphics and Image Processing 14 (1980), 227248.
 7.
K. Deckelnick and C.M. Elliott, Uniqueness and error analysis for HamiltonJacobi equations with discontinuities, preprint (2003).
 8.
Lawrence
C. Evans, Partial differential equations, Graduate Studies in
Mathematics, vol. 19, American Mathematical Society, Providence, RI,
1998. MR
1625845 (99e:35001)
 9.
Marizio
Falcone and Roberto
Ferretti, Discrete time highorder schemes for viscosity solutions
of HamiltonJacobiBellman equations, Numer. Math. 67
(1994), no. 3, 315–344. MR 1269500
(95d:49045), http://dx.doi.org/10.1007/s002110050031
 10.
M.
Falcone and R.
Ferretti, SemiLagrangian schemes for HamiltonJacobi equations,
discrete representation formulae and Godunov methods, J. Comput. Phys.
175 (2002), no. 2, 559–575. MR 1880118
(2003f:65151), http://dx.doi.org/10.1006/jcph.2001.6954
 11.
J. Helmsen, E. Puckett, P. Colella, and M. Dorr, Two new methods for simulating photolithography development in 3d, Proc. SPIE 2726 (1996), 253261.
 12.
C.Y. Kao, S. Osher, and J. Qian, LaxFriedrichs sweeping scheme for static HamiltonJacobi equations, UCLA CAM report (2003).
 13.
S. Kim, An level set method for Eikonal equations, SIAM J. Sci. Comput. (2001).
 14.
Elisabeth
Rouy and Agnès
Tourin, A viscosity solutions approach to shapefromshading,
SIAM J. Numer. Anal. 29 (1992), no. 3, 867–884.
MR
1163361 (93d:65019), http://dx.doi.org/10.1137/0729053
 15.
W. A. J. Schneider, K. A. Ranzinger, A. H. Balch, and C. Kruse, A dynamic programming approach to first arrival traveltime computation in media with arbitrarily distributed velocities, Geophysics (1992).
 16.
J.
A. Sethian, A fast marching level set method for monotonically
advancing fronts, Proc. Nat. Acad. Sci. U.S.A. 93
(1996), no. 4, 1591–1595. MR 1374010
(97c:65171), http://dx.doi.org/10.1073/pnas.93.4.1591
 17.
Yenhsi
Richard Tsai, Rapid and accurate computation of the distance
function using grids, J. Comput. Phys. 178 (2002),
no. 1, 175–195. MR 1899139
(2003e:65029), http://dx.doi.org/10.1006/jcph.2002.7028
 18.
Y.R. Tsai, L.T Cheng, S. Osher, and H.K. Zhao, Fast sweeping algorithms for a class of HamiltonJacobi equations, SIAM J. Numer. Anal. 41 (2003), no. 2, 673694.
 19.
John
N. Tsitsiklis, Efficient algorithms for globally optimal
trajectories, IEEE Trans. Automat. Control 40 (1995),
no. 9, 1528–1538. MR 1347833
(96d:49039), http://dx.doi.org/10.1109/9.412624
 20.
H.K. Zhao, Analysis and visualization of large set of unorganized data points using the distance function, preprint (2002).
 21.
H.K. Zhao, S. Osher, B. Merriman, and M. Kang, Implicit and nonparametric shape reconstruction from unorganized points using variational level set method, Computer Vision and Image Understanding 80 (2000), no. 3, 295319.
 1.
 M. Bardi and S. Osher, The nonconvex multidimensional Riemann problem for HamiltonJacobi equations, SIAM Anal. 22(2) (1991), 344351. MR 91k:35056
 2.
 M. Boué and P. Dupuis, Markov chain approximations for deterministic control problems with affine dynamics and quadratic cost in the control, SIAM J. Numer. Anal. 36 (1999), no. 3, 667695. MR 2000a:49054
 3.
 B. Cockburn and J. Qian, A short introduction to continuous dependence results for HamiltonJacobi equations, Collected Lectures on the Preservation of Stability Under Discretization (D. Estep and S. Tavener, Eds.), SIAM, 2002.
 4.
 M.G. Crandall and P.L. Lions, Viscosity solutions of HamiltonJacobi equations, Trans. Amer. Math. Soc. 277 (1983) no. 1, 142. MR 85g:35029
 5.
 , Two approximations of solutions of HamiltonJacobi equations, Math. Comp. 43 (1984), no. 167, 119. MR 86j:65121
 6.
 P. Danielsson, Euclidean distance mapping, Computer Graphics and Image Processing 14 (1980), 227248.
 7.
 K. Deckelnick and C.M. Elliott, Uniqueness and error analysis for HamiltonJacobi equations with discontinuities, preprint (2003).
 8.
 Lawrence C. Evans, Partial differential equations, Graduate Studies in Mathematics, vol. 19, AMS, 1998. MR 99e:35001
 9.
 M. Falcone and R. Ferretti, Discrete time highorder schemes for viscosity solutions of HamiltonJacobiBellman equations, Numer. Math. 7 (1994), no. 3, 315344. MR 95d:49045
 10.
 , SemiLagrangian schemes for HamiltonJacobi equations, discrete representation formulae and Godunov methods, J. Comput. Phys. 175 (2002), no. 2, 559575. MR 2003f:65151
 11.
 J. Helmsen, E. Puckett, P. Colella, and M. Dorr, Two new methods for simulating photolithography development in 3d, Proc. SPIE 2726 (1996), 253261.
 12.
 C.Y. Kao, S. Osher, and J. Qian, LaxFriedrichs sweeping scheme for static HamiltonJacobi equations, UCLA CAM report (2003).
 13.
 S. Kim, An level set method for Eikonal equations, SIAM J. Sci. Comput. (2001).
 14.
 E. Rouy and A. Tourin, A viscosity solution approach to shapefromshading, SIAM J. Num. Anal. 29 (1992), no. 3, 867884. MR 93d:65019
 15.
 W. A. J. Schneider, K. A. Ranzinger, A. H. Balch, and C. Kruse, A dynamic programming approach to first arrival traveltime computation in media with arbitrarily distributed velocities, Geophysics (1992).
 16.
 J.A. Sethian, A fast marching level set method for monotonically advancing fronts, Proc. Nat. Acad. Sci. 93 (1996), no. 4, 15911595. MR 97c:65171
 17.
 Y.R. Tsai, Rapid and accurate computation of the distance function using grids, J. Comp. Phys. 178 (2002), no. 1, 175195. MR 2003e:65029
 18.
 Y.R. Tsai, L.T Cheng, S. Osher, and H.K. Zhao, Fast sweeping algorithms for a class of HamiltonJacobi equations, SIAM J. Numer. Anal. 41 (2003), no. 2, 673694.
 19.
 J.N. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Transactions on Automatic Control 40 (1995), no. (9), 15281538.MR 96d:49039
 20.
 H.K. Zhao, Analysis and visualization of large set of unorganized data points using the distance function, preprint (2002).
 21.
 H.K. Zhao, S. Osher, B. Merriman, and M. Kang, Implicit and nonparametric shape reconstruction from unorganized points using variational level set method, Computer Vision and Image Understanding 80 (2000), no. 3, 295319.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
65N06,
65N12,
65N15,
35L60
Retrieve articles in all journals
with MSC (2000):
65N06,
65N12,
65N15,
35L60
Additional Information
Hongkai Zhao
Affiliation:
Department of Mathematics, University of California, Irvine, California 926973875
Email:
zhao@math.uci.edu
DOI:
http://dx.doi.org/10.1090/S0025571804016783
PII:
S 00255718(04)016783
Keywords:
Eikonal equation,
characteristics,
Godunov scheme,
upwind difference,
GaussSeidel iteration,
CourantFriedrichsLewy (CFL) condition
Received by editor(s):
September 20, 2003
Published electronically:
May 21, 2004
Additional Notes:
This work was partially supported by the Sloan Fundation, ONR grant N000140210090 and DARPA grant N000140210603
Article copyright:
© Copyright 2004
American Mathematical Society
