Introduction

A recently introduced method for solving the eikonal equation, named the fast marching method Sethian and Popovici (1997); Sethian (1996), has two very intriguing features: it is unconditionally stable and, at the same time, highly efficient. Essentially, the 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). Additionally, a minimum traveltime tree is constructed using fast algorithms (heap sorting) and can be maintained at a computational cost proportional to $\log N$, where N is the number of grid points in the computational domain. As a result, the cost of the eikonal solver is roughly proportional to $N\log N$. The minimum-time requirement ensures the method's stability no matter how complicated the velocity model is.

However, this new solver has a problem. It 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, particularly in two cases:

• When there is large wavefront curvature, such as near the source
• When the wavefront propagation is diagonal to the grid orientation

Higher-order approximations of the traveltime derivatives could reduce these errors, but at a considerably larger cost.

In this paper, we investigate a possibility of reducing the computational errors by implementing the fast marching solver in spherical coordinates. The ability to handle turning waves is usually considered the main advantage of solving the eikonal equation in polar coordinates Fowler (1994); Popovici (1991); Schneider (1993); van Trier and Symes (1991). Turning waves, however, do not present a problem with this new scheme; the method can, by design, handle wavefronts at any angle, provided that they correspond to the first arrival. Nevertheless, the importance of the polar coordinates in the fast marching approach should not be underestimated. Compared with the Cartesian-coordinates implementation of the fast marching algorithm, in simple and complex velocity models, we show that the polar coordinate implementation can considerably improve the accuracy of the solution at practically no loss in the computational efficiency.