Traveltime computation is one of the most important tasks in seismic
processing (Kirchhoff depth migration and related methods) and
modeling. The traveltime field of a fixed source in a heterogeneous
medium is governed by the eikonal equation, derived about 150 years
ago by Sir William Rowan Hamilton. A direct numerical solution of the
eikonal equation has become a popular method of computing traveltimes
on regular grids, commonly used in seismic imaging
Podvin and Lecomte (1991); Vidale (1990); van Trier and Symes (1991). A recent
contribution to this field is the *fast marching* level set
method, developed by Sethian (1996a) in the general context of level
set methods for propagating interfaces Osher and Sethian (1988); Sethian (1996b). Sethian and
Popovici 1997 report a successful application of this
method in three-dimensional seismic computations. The fast marching
method belongs to the family of upwind finite-difference schemes aimed
at providing the *viscosity* solution Lions (1982), which
corresponds to the first-arrival branch of the traveltime field. The
remarkable stability of the method results from a specifically chosen
order of finite-difference evaluation. The order selection scheme
resembles the *expanding wavefronts* method of Qin et al. (1992).
The fast speed of the method is provided by the heap sorting
algorithm, commonly used in Dijkstra's shortest path computation
methods Cormen et al. (1990). A similar idea has been used previously in a
slightly different context, in the *wavefront tracking* algorithm
of Cao and Greenhalgh (1994).

In this paper, I address the question of evaluating the fast marching method's applicability to more general situations. I describe a simple interpretation of the algorithm in terms of variational principles (namely, Fermat's principle in the case of eikonal solvers.) Such an interpretation immediately yields a useful extension of the method for unstructured grids: triangulations in two dimensions and tetrahedron tesselations in three dimensions. It also provides a constructive way of applying similar algorithms to solving other eikonal-like equations: anisotropic eikonal Dellinger (1991), ``focusing'' eikonal Biondi et al. (1997), kinematic offset continuation Fomel (1995), and kinematic velocity continuation Fomel (1996). Additionally, the variational formulation can give us hints about higher-order enhancements to the original first-order scheme.

10/9/1997