Fast Marching Methods

TLDR

Fast Marching Methods are numerical schemes for solving the nonlinear Eikonal and related static Hamilton–Jacobi equations, and are applied to shape offsetting, distance computation, shape‑from‑shading, photolithography, seismic travel‑time first arrivals, shortest geodesics, optimal path planning, and visibility calculations. This paper reviews the development of Fast Marching Methods, detailing their theoretical and numerical foundations, higher‑order variants, and demonstrating their use across diverse application areas. The methods employ entropy‑satisfying upwind schemes combined with fast sorting techniques to produce consistent, accurate, and highly efficient algorithms. The algorithms achieve optimal computational complexity of O(N log N), where N is the number of points in the domain.

Abstract

Fast Marching Methods are numerical schemes for computing solutions to the nonlinear Eikonal equation and related static Hamilton--Jacobi equations. Based on entropy-satisfying upwind schemes and fast sorting techniques, they yield consistent, accurate, and highly efficient algorithms. They are optimal 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 are of use in a variety of applications, including problems in shape offsetting, computing distances from complex curves and surfaces, shape-from-shading, photolithographic development, computing first arrivals in seismic travel times, construction of shortest geodesics on surfaces, optimal path planning around obstacles, and visibility and reflection calculations. In this paper, we review the development of these techniques, including the theoretical and numerical underpinnings; provide details of the computational schemes, including higher order versions; and demonstrate the techniques in a collection of different areas.