Next: Solving the eikonal equation Up: Fomel: Fast marching Previous: The theoretic grounds of

# Variational principles on a grid

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)
Now let us consider an arbitrary point C in the vicinity of AB. If we know that the ray from the source to C passes through some point of the segment AB, then the total traveltime at C is approximately
 (10)
where sC is the local slowness, corresponds to the projection of C to the line AB (normalized by the length |AB|), and is the length of the normal from C to .

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)
which has (as a quadratic equation) the explicit solution for :
 (12)
Finally, substituting the value of from (12) into equation (10) and selecting the appropriate branch of the square root, we obtain the formula

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)
We can notice that (14) is precisely equivalent to the solution of the quadratic equation (13), which in our new notation takes the form
 (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.

Next: Solving the eikonal equation Up: Fomel: Fast marching Previous: The theoretic grounds of
Stanford Exploration Project
10/9/1997