The fast-marching algorithm consists of two parts: minimum traveltime selection and a local traveltime updating scheme. The selection scheme is essentially based on Fermat's principle. The local traveltime updating scheme can also be derived from the same principle using a local linear interpolation, which provides the first-order accuracy.

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

For simplicity, let us focus on the 2-D case
Consider a line segment with the end points *A* and *B*,
as shown in Figure 6. 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

(6) |

(7) |

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

(8) |

(9) |

(10) |

The above general procedure can be greatly simplified when applied to some regular grids, such as the rectangular grid or the tetragonal grid. This expression is even valid for unstructured grids. As pointed out by Fomel 1997, unstructured grids have some attractive computational advantages over the regular ones. Moreover, 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.

7/5/1998