How to Learn the Fast Marching Method: Eikonal Equations, Accepted Fronts, Upwind Updates and Arrival-Time Computation

Wait, What?

A continuous wavefront can be computed with a priority queue in a way that feels strikingly similar to Dijkstra’s algorithm.

The Fast Marching Method (FMM) computes arrival times for fronts that move monotonically through a domain. Its classic target is the Eikonal equation, often written |∇T(x)|F(x)=1, where T is arrival time and F is local propagation speed. James Sethian’s 1996 method combines an upwind finite-difference discretisation with a smallest-arrival-time ordering so that accepted values never need to be revisited under the standard assumptions.

Quick Answer

Learn Fast Marching through arrival-time intuition → Eikonal equation → grid discretisation → FAR/TRIAL/ACCEPTED states → upwind local solve → min-priority queue → monotone acceptance → complexity → path extraction → variable speed and numerical boundaries. Do not start by copying a PDE solver. First understand why the smallest tentative arrival time can become final.

1. Start With a Front, Not a Formula

Imagine a spark igniting a uniform sheet. If the flame moves at one unit of distance per unit time, the arrival time at a point is simply its distance from the ignition source. If some regions allow faster travel and others slower travel, the arrival-time contours bend. The Eikonal equation describes this relationship between the gradient of arrival time and local speed.

Fast Marching computes that arrival-time field efficiently when the front advances outward monotonically.

2. The Three-State Mental Model

• ACCEPTED / Known: arrival time is final.
• TRIAL / Considered: has a tentative value and sits on the current numerical front.
• FAR: not yet reached; arrival time is effectively infinity.

Seed points start with known arrival times, often zero. Their neighbours become TRIAL. Repeatedly take the TRIAL node with the smallest tentative time, mark it ACCEPTED, update its unaccepted neighbours, and continue.

3. Why This Resembles Dijkstra

Dijkstra repeatedly finalises the unsettled graph vertex with the smallest tentative distance. Fast Marching repeatedly finalises the grid node with the smallest tentative arrival time. The resemblance is real, but the local update differs: FMM solves a discretised PDE using neighbouring accepted arrival times rather than simply adding a fixed edge weight.

This boundary prevents a common misunderstanding: Fast Marching is not merely “Dijkstra on a grid.” It uses causality from an upwind Eikonal discretisation.

4. The Upwind Idea

Arrival information should come from directions the front has already reached. In a two-dimensional Cartesian grid, the local Eikonal update uses the smallest accepted neighbour in each coordinate direction. For uniform spacing h and speed F, a standard first-order update solves a quadratic relation of the form:

((T - a)/h)^2 + ((T - b)/h)^2 = 1/F^2

subject to the upwind condition that the new T should not precede the accepted neighbour values used to compute it. If the two-neighbour quadratic is not causally valid, the update falls back to a one-sided form.

5. Work a Uniform-Speed Grid by Hand

Start with a 7×7 grid, unit spacing and a central seed with T=0. Mark the four immediate axis neighbours as TRIAL and compute their values. Accept the smallest. Continue for a few steps and sketch equal-arrival-time contours. On a sufficiently fine uniform grid, they approximate expanding circles even though the computation occurs on a Cartesian lattice.

Then halve the speed in one rectangular region. Predict how arrival contours should bend before rerunning the updates. The learner should see the algorithm choosing faster routes through the continuous speed field rather than blindly minimising Euclidean distance.

6. The Core Loop

initialize all nodes FAR with T = infinity
set source nodes ACCEPTED with known T
update their neighbours and place them in min-priority queue as TRIAL

while priority queue is not empty:
    x = TRIAL node with smallest tentative T
    if x already ACCEPTED: continue
    mark x ACCEPTED

    for each non-ACCEPTED neighbour y:
        newT = upwind_eikonal_update(y)
        if newT improves T[y]:
            T[y] = newT
            push/update y in priority queue

Production code must specify heap update strategy, boundary conditions, grid spacing, obstacles, anisotropy assumptions and the local numerical stencil.

7. Why Accepted Values Stay Final

The method relies on a causality property: the upwind discretisation lets information propagate from smaller arrival times toward larger ones. Selecting the smallest TRIAL value ensures that no later front can legitimately reach that node earlier under the isotropic monotone model. This is why Fast Marching can be single-pass in the sense that ACCEPTED values do not need iterative correction.

8. Complexity

For N grid nodes, a binary heap gives the familiar O(N log N) priority-queue profile under standard implementations. Specialized heaps or restricted value ranges can change constants or theoretical bounds. The local Eikonal update is constant-size for a fixed-dimensional stencil.

The professional question is not just asymptotic cost. Memory layout, heap behaviour, grid dimension, obstacle representation and cache locality all matter on large domains.

9. From Arrival Times to Paths

FMM produces a scalar arrival-time field. To recover a route from a destination back toward a source, one can descend along the negative gradient of T, with interpolation and numerical care. The resulting route is connected to the continuous metric induced by the speed field, not necessarily to a path through discrete parent pointers.

10. Where Fast Marching Fits

Fast Marching is used in level-set methods, computational geometry, image analysis, medical imaging, robotics, geophysics and travel-time computation. Current scientific software still exposes FMM solvers; for example, Pyrocko’s 2026 library documents a 2D/3D Cartesian Eikonal solver explicitly based on Sethian’s 1996 method.

11. Where It Does Not Fit

• fronts that must move backward as well as forward;
• strongly anisotropic propagation without an appropriate generalized method;
• problems where the discretisation violates the causality assumptions;
• dynamic environments where recomputing the whole arrival field is wasteful and an incremental method is more suitable.

Fast Sweeping, ordered upwind methods, level-set solvers and graph shortest-path algorithms solve related but not identical numerical jobs.

12. Beginner → Professional Learning Progression

• Beginner: draw wavefront arrival times at constant speed.
• Foundation: trace FAR/TRIAL/ACCEPTED state changes with a priority queue.
• Intermediate: derive and implement the first-order two-dimensional upwind update.
• Advanced: handle obstacles, variable speed and gradient-based path extraction.
• Professional: validate convergence under grid refinement, compare FMM with Dijkstra and Fast Sweeping, profile heaps and stencils, and state clearly when isotropic causality assumptions fail.

13. Common Failure States

• Accepting the newest TRIAL node instead of the smallest-time node.
• Using non-upwind neighbours in the local PDE update.
• Solving the quadratic but ignoring the causality condition.
• Confusing a zero-speed obstacle with a merely slow region.
• Extracting paths by stepping to the smallest adjacent cell only and calling that continuous gradient descent.
• Applying isotropic FMM to anisotropic physics without justification.
• Comparing arrival times across different grid resolutions without a convergence check.

14. How to Learn It Efficiently

Start with a state trace rather than PDE code. Predict which TRIAL node will be accepted next, run the step, and investigate surprises. Then isolate the local Eikonal update as a separate worked example before combining it with the heap loop. Faded Parsons-style reconstruction is useful here because learners can first reason about the ordering of state transitions and only later write all numerical details from scratch.

15. Learning Hall Boundary

This article owns the Fast Marching Method for monotone Eikonal arrival-time computation on discretised domains. It does not replace the existing Dijkstra, A*, Jump Point Search, D* Lite, numerical-integration or generic PDE owners.

Evidence Boundary and Further Reading

The canonical reference is James A. Sethian, “A fast marching level set method for monotonically advancing fronts,” Proceedings of the National Academy of Sciences 93(4), 1996. Sethian’s Berkeley materials explain the boundary-value formulation and its connection to Dijkstra-like accepted-front ordering.

• PNAS — Sethian 1996
• UC Berkeley — Fast Marching explanation
• Pyrocko 2026 — current FMM Eikonal solver documentation
• ACM — PRIMM programming pedagogy

Professional rule: you understand Fast Marching when you can justify why the next minimum tentative arrival becomes final, derive the local upwind update, and state exactly which physical and numerical assumptions make that causality argument valid.