(1) |

The fast marching method solves equation (1) by directly mimicking the advancing wavefront. Every point on the computational grid is classified into three groups: points behind the wavefront, whose traveltimes are known and fixed; points on the wavefront, whose traveltimes have been calculated, but are not yet fixed; and points ahead of the wavefront. The algorithm then proceeds as follows:

- 1.
- Choose the point on the wavefront with the smallest traveltime.
- 2.
- Fix this traveltime.
- 3.
- Advance the wavefront, so that this point is behind it, and adjacent points are either on the wavefront or behind it.
- 4.
- Update traveltimes for adjacent points on the wavefront by solving equation (1) numerically.
- 5.
- Repeat until every point is behind the wavefront.

The update procedure (step 4.) requires the solution of the following
quadratic equation for *t*,

(2) |

(3) |

If we choose a two-point finite-difference operator, such as

(4) | ||

(5) |

This two-point stencil, however, is only accurate to first-order. If instead we choose a suitable three-point finite-difference stencil, we may expect the method to have second-order accuracy. For example, the second-order upwind stencil,

(6) | ||

(7) |

4/20/1999