Fast marching methods

Fast Marching Methods are numerical schemes for computing solutions to the nonlinear Eikonal equation and related static Hamilton-Jacobi equations. Ba sed on entropy-satisfying upwind schemes and fast sorting techniques, they yield consistent, accurate, and highly efficient algorithms. They are optim al in the sense that the computational complexity of the algorithms is O(N log N), where N is the total number of points in the domain. The schemes ar e of use in a variety of applications, including problems in shape offsetti ng, computing distances from complex curves and surfaces, shape-from-shadin g, photolithographic development, computing first arrivals in seismic trave l times, construction of shortest geodesics on surfaces, optimal path plann ing around obstacles, and visibility and reflection calculations. In this p aper, we review the development of these techniques, including the theoreti cal and numerical underpinnings; provide details of the computational schem es, including higher order versions; and demonstrate the techniques in a co llection of different areas.