Sethian (1996) and Sethian and Popovici (1997) recently introduced a method for solving the eikonal equation that
they refer to as the *fast marching* method. Their eikonal solver has two very
important features: it is unconditionally stable and, at the same
time, highly efficient. Their method is based on solving the eikonal equation on
a Cartesian grid along the wavefront,
starting with those points with minimum traveltime--an idea similar
to the method of *expanding wavefronts* Qin et al. (1992).
As a result, a minimum traveltime tree is constructed using fast
algorithms (heap sorting) with computational
cost proportional to , where *N* is the number of grid points
in the computational domain. Therefore, the cost of the eikonal
solver is roughly proportional to .By starting traveltime calculation from those points with minimum traveltime, the stability
of the algorithm is ensured regardless of the complexity of the
velocity model.

The impressive features of the fast marching method, stability and efficiency, are achieved at the expense of accuracy. The approach is based on a first-order approximation of the traveltime derivatives with respect to position. This low-order approximation can result in relatively large traveltime errors when the wavefront curvature is large and the wavefront propagation is diagonal to the grid orientation. In Cartesian coordinates, spherical wavefronts can spend a long time satisfying these two destructive conditions. As a result, implementation of the fast marching method in the Cartesian coordinate, unless the gird is very fine, can result in relatively large errors. Recently, Alkhalifah and Fomel (1997) suggested a spherical coordinate implementation of the fast marching method. In spherical coordinates, wavefronts emanating from a source typically spend less time traveling diagonally with respect to the coordinate system than the case in Cartesian coordinates. As a result, spherical coordinate implementation achieves more accurate traveltimes even for complex models like the Marmousi model, without compromising stability or efficiency.

The SEG/EAGE 3-D velocity model was used to generate 3-D prestack synthetic datasets. These datasets are commonly used to test migration algorithms, especially 3-D prestack Kirchhoff ones. At the center of a 3-D Kirchhoff-based migration is 3-D traveltime computation, and the quality of the migration depends heavily on the accuracy of the traveltime calculation. Thus, the 3-D slat-dome velocity model is useful for testing 3-D traveltime calculation methods, including the fast marching method, which is the main focus here.

In this paper, I will highlight the benefits of executing the fast marching method of traveltime calculation in spherical coordinates. To show these benefits, I will use the SEG/EAGE 3-D salt-dome velocity model. The complexity of the 3-D salt structure provides us with a good measure of the accuracy of spherical coordinate implementation. We will also look into the role that head-waves and other low, but fast, energy arrivals play in traveltime maps.

7/5/1998