Three-dimensional travel-time computation using the Fast marching method

We present a fast algorithm for solving the eikonal equation in three dimensions, based on the Fast Marching Method (FMM). The algorithm is of order O(N log N), where N is the total number of grid points in the computational domain. The algorithm can be used in any orthogonal coordinate system, and globally constructs the solution to the eikonal equation for each point in the coordinate domain. The method is unconditionally stable, and constructs solutions consistent with the exact solution for arbitrarily large gradient jumps in velocity. In addition, the method resolves any overturning propagation wavefronts. We begin with the mathematical foundation for solving the eikonal equation using the FMM, and follow with the numerical details. We show examples of traveltime propagation through the SEG/EAGE Salt Model, and the use of these first arrival traveltimes to image 3D prestack data.