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
Figure 3 A geometrical scheme for the traveltime updating procedure in two dimensions. |
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 tA and tB 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 tC 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
Figure 4 A geometrical scheme for traveltime updating on a rectangular grid. |
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.