3-D traveltime computation using the fast marching method

We present a fast algorithm for solving the eikonal equation in three dimen sions: based on the fast marching method. The algorithm is of the order O(N log N), where N is the total number of grid points in the computational do main. The algorithm can be used in any orthogonal coordinate system and glo bally constructs the solution to the eikonal equation for each point in the coordinate domain. The method is unconditionally stable and constructs sol utions consistent with the exact solution for arbitrarily large gradient ju mps in velocity. In addition, the method resolves any overturning propagati on wavefronts. We begin with the mathematical foundation for solving the eikonal equation using the fast marching method and follow with the numerical details. We th en show examples of traveltime propagation through the SEG/EAGE salt model using point-source and planewave initial conditions and analyze the error i n constant velocity media. The algorithm allows for any shape of the initial wavefront. While a point source is the most commonly used initial condition, initial plane waves can be used for controlled illumination or for downward continuation of the tr aveltime field from one depth to another or from a topographic depth-surfac e to another. The algorithm presented here is designed for computing first- arrival traveltimes. Nonetheless, since it exploits the fast marching metho d for solving the eikonal equation, we believe it is the fastest of all pos sible consistent schemes to compute first arrivals.