In this section, I derive a discrete traveltime computation procedure, based solely on Fermat's principle, and show that on a Cartesian rectangular grid it is precisely equivalent to the update formula (1) of the first-order eikonal solver.

triangle
A geometrical scheme for the
traveltime updating procedure in two dimensions.
Figure 3 |

For simplicity, let us focus on the two-dimensional case^{}. Consider a line segment with the end points *A* and *B*,
as shown in Figure 3. Let *t*_{A} and *t*_{B} denote the
traveltimes from a fixed distant source to points *A* and *B*,
respectively. Define a parameter such that at *A*,
at *B*, and changes continuously on the line segment
between *A* and *B*. Then for each point of the segment, we can
approximate the traveltime by the linear interpolation formula

(9) |

(10) |

Fermat's principle states that the actual ray to *C* corresponds to a
local minimum of the traveltime with respect to raypath perturbations.
According to our parameterization, it is sufficient to find a local
extreme of *t*_{C} with respect to the parameter . Equating the
derivative to zero, we arrive at the equation

(11) |

(12) |

where *c* = |*AB*|, *a* = |*BC*|, *b* = |*AC*|, angle corresponds to , and angle corresponds to
in the triangle *ABC* (Figure 3).

square
A geometrical scheme for
traveltime updating on a rectangular grid.
Figure 4 |

To see the connection of formula (13) with the eikonal
difference equation (1), we need to consider the case
of a rectangular computation cell with the edge *AB* being a diagonal
segment, as illustrated in Figure 4. In this case,
, , , and formula (13) reduces to

(14) |

(15) |

What have we accomplished by this analysis? First, we have derived a local traveltime computation formula for an arbitrary grid. The derivation is based solely on Fermat's principle and a local linear interpolation, which provides the first-order accuracy. Combined with the fast marching evaluation order, which is also based on Fermat's principle, this procedure defines a complete algorithm of first-arrival traveltime calculation. On a rectangular grid, this algorithm is exactly equivalent to the fast marching method of Sethian (1996a) and Sethian and Popovici (1997). Second, the derivation provides a general principle, which can be applied to derive analogous algorithms for other eikonal-type (Hamilton-Jacobi) equations and their corresponding variational principles.

10/9/1997