Numerical analysis Time-dependent partial differential equations Proposition

Fast marching method

Builds on Eikonal equation Heap Viscosity solution

Statement

Let $h > 0$ and let $G$ be a finite set of $N$ nodes $x_{ij} = (ih, jh)$ of a square grid in $\R^2$ . Let $F_{ij} > 0$ be a speed at each node, and let $S \subset G$ be a nonempty set of source nodes with given values $T_{ij} \ge 0$ . For $T$ on $G$ write $a = \min(T_{i-1,j}, T_{i+1,j})$ and $b = \min(T_{i,j-1}, T_{i,j+1})$ , with missing neighbours ignored. The upwind discretization of the eikonal equation $\abs{\nabla T} = 1/F$ at a node $x_{ij} \notin S$ is $\big( \max(T_{ij} - a, 0) \big)^2 + \big( \max(T_{ij} - b, 0) \big)^2 = \frac{h^2}{F_{ij}^2}.$ The fast marching method first marks the nodes of $S$ as accepted. It then repeats two steps until all nodes are accepted. First, it computes a tentative value at each non-accepted neighbour of an accepted node. This value solves the equation above, with only accepted neighbours used in $a$ and $b$ . Second, it accepts the node with the smallest tentative value. Assume the grid graph on $G$ is connected. Then:

every node is accepted exactly once, and the method stops;
the nodes not in $S$ are accepted in nondecreasing order of their values;
the final values satisfy the upwind equation at every node not in $S$ ;
with the tentative values kept in a binary heap, the method uses $O(N \log N)$ operations.

Remarks

The upwind equation has the causality property: its solution $T_{ij}$ is larger than every neighbour value that enters it with a nonzero term. Hence a newly computed tentative value is never smaller than the last accepted value, which gives claim 2, and accepting the smallest tentative value never needs to be undone. The source values are arbitrary, so claim 2 is only about the nodes outside $S$ . This is the same argument as for Dijkstra's algorithm, which the method resembles; Dijkstra's algorithm on the grid graph would measure distance along grid edges only. Each node is inserted and updated a bounded number of times, and each heap operation costs $O(\log N)$ , which gives claim 4.

Example: with $F \equiv 1$ and one source with $T = 0$ at the origin, the computed $T$ approximates the Euclidean distance to the origin. At the node $(h, h)$ , both neighbours $(h, 0)$ and $(0, h)$ have value $h$ , and the equation gives $T = h + h/\sqrt{2} \approx 1.71 h$ , near the true value $\sqrt{2} h \approx 1.41 h$ . The error is of first order in $h$ .

Going deeper

For a student

The eikonal equation is a stationary Hamilton–Jacobi equation, and its relevant solution is the viscosity solution. The upwind scheme above is monotone and consistent, and as $h \to 0$ its solutions approximate the viscosity solution. The fast marching method solves this nonlinear system in one pass, instead of by repeated sweeps or iterations. It is used to build signed distance functions for the level-set method, to compute shortest paths around obstacles, and in seismic travel time computations.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Eikonal equation concept
Heap concept
Viscosity solution concept
Fast marching method statement

Tag	`DAK6EJK20R`
URI	`m2://DAK6EJK20R`
Kind	statement, proposition
Writing	W0 stub
MSC	65N06, 35F21, 65D18
Status	This copy of the site has no build data. Run `m2 status DAK6EJK20R`.
About	Eikonal equation
Uses	Eikonal equation, Heap, Viscosity solution
Same as	Wikidata Q5437042 Wikipedia Fast marching method