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

Wait, What?

Dijkstra’s algorithm can become a numerical PDE solver when “distance” is replaced by arrival time and local geometry determines the edge cost.

The Fast Marching Method (FMM) computes arrival times for a front that moves monotonically through a domain. It solves the Eikonal equation in settings where information propagates outward and never needs to reverse direction. The method combines an upwind finite-difference update with a priority queue, giving an O(N log N) algorithm for N grid points in the standard implementation.

Quick Answer

Learn FMM through wavefront intuition → arrival-time function → Eikonal equation → known/trial/far states → upwind discretization → local quadratic update → min-priority queue → causality → variable speed → geodesics and applications → numerical accuracy and limitations. The crucial idea is that once the smallest trial value is accepted, causality guarantees it will not need to decrease later.

1. Begin With a Spreading Front

Imagine ink expanding across paper, a wildfire moving through terrain, or a wavefront propagating through a medium. Instead of simulating the moving curve at every instant, define T(x): the time at which the front first reaches position x.

If the front speed is F(x)>0, the arrival-time field satisfies the Eikonal equation:

F(x) |grad T(x)| = 1

Where travel is fast, arrival-time contours spread farther apart. Where travel is slow, they crowd together.

2. See the Connection to Shortest Paths

If speed is constant, T behaves like distance from the source divided by speed. On a grid, a crude approach could use graph shortest paths. Fast Marching instead uses a continuous-space-inspired upwind discretization, producing a better approximation to the Eikonal PDE than simply assigning fixed edge weights to lattice moves.

The conceptual similarity to Dijkstra is still important: always finalize the currently smallest tentative arrival time.

3. The Three State Sets

• Accepted/Known: arrival time is finalized.
• Trial/Narrow Band: neighbours of the accepted region with tentative values.
• Far: not yet reached by the computational front.

A min-priority queue stores trial points by tentative arrival time. Repeatedly pop the smallest trial value, accept it, update its neighbours, and continue.

4. Why the Upwind Update Matters

The PDE says information flows from smaller arrival times toward larger ones. A valid finite-difference update therefore uses already accepted neighbouring values on the upwind side. In two dimensions with grid spacing h and local speed F, let a and b be the smallest accepted horizontal and vertical neighbour times. A common first-order update solves:

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

subject to the causal requirement that T is not smaller than the neighbours used to compute it.

5. Work the One-Dimensional Case First

On a 1D grid with constant speed F=1 and spacing h=1, a source at index 0 gives arrival times 0,1,2,3,… . FMM looks trivial here, which is exactly why the case is useful: the accepted front moves monotonically and every new value depends only on the already accepted neighbour behind it.

Then move to a 2D grid and observe how diagonal propagation emerges from the quadratic update rather than from hard-coded diagonal edges.

6. Derive the Local Quadratic Carefully

When both orthogonal neighbours contribute, expanding the equation gives a quadratic in T. If the two-neighbour solution violates the upwind condition, fall back to a one-neighbour update. This distinction is where many textbook implementations become buggy.

Professional code should encapsulate the local solver and test it independently before integrating it with the heap.

7. The Dijkstra-Like Main Loop

initialize all T = infinity
set source T = 0 and mark accepted
update source neighbours and place them in min-heap

while heap not empty:
    x = pop smallest trial value
    if x already accepted: continue
    mark x accepted

    for each neighbour y of x:
        if y not accepted:
            newT = upwind_update(y)
            if newT improves T[y]:
                T[y] = newT
                push/update y in heap

The heap provides the O(log N) ordering step, leading to O(N log N) total complexity in the standard formulation.

8. Causality Is the Algorithmic Contract

Fast Marching works because the front is monotone and local updates depend on smaller arrival times. Once a point is accepted as the smallest trial value, no later event should create a smaller valid arrival time for it. That one-pass property is the numerical analogue of Dijkstra’s nonnegative-edge logic.

If the governing dynamics allow information to move backward or require repeated correction, another method may be needed.

9. Variable Speed Changes the Geometry

When F(x) varies, the fastest route may bend around slow regions. Fast Marching therefore computes not merely Euclidean distance but a travel-time metric induced by the speed field. This is why it appears in seismic first-arrival calculations, robot navigation, medical imaging, computer vision and geodesic computation.

10. Extract a Path From the Arrival-Time Field

Once T is known, a shortest-time path to a source can often be recovered by descending the arrival-time gradient from the target. On a discrete grid, use careful interpolation or neighbour-based descent. The arrival field and the path-extraction procedure are separate jobs and should be validated separately.

11. Accuracy and Grid Effects

First-order Fast Marching is efficient but introduces discretization error. Coarse grids can produce visible anisotropy and staircase effects. Higher-order updates, unstructured meshes and specialized variants improve accuracy, but each adds complexity and may change stability requirements.

The right benchmark therefore compares against an analytic solution where possible, not only against another implementation.

12. Current Implementations and Scope

The scikit-fmm project implements Fast Marching for Eikonal boundary-value problems and documents the standard form F(x)|∇T(x)|=1. Sethian’s Berkeley materials and SIAM Review article remain authoritative foundations for the theory, numerical causality and applications.

13. Fast Marching Versus Fast Sweeping and Level Sets

Fast Marching is best suited to monotonically advancing fronts with a causal ordering. Fast Sweeping uses directional relaxation sweeps and can be attractive for some Eikonal problems. General level-set methods handle interfaces that can move in more complicated ways, including situations without a single monotone arrival-time ordering.

Knowing when not to use FMM is part of professional mastery.

14. How to Learn It Efficiently

Use Predict–Run–Investigate–Modify–Make. Predict arrival times on a 1D line. Run a tiny constant-speed implementation. Investigate the heap and accepted-front order. Modify a region’s speed and predict how the path bends. Then make a 2D solver with tests for the local quadratic update.

A subgoal-labelled worked example should separate: choose upwind neighbours, solve local equation, check causality, update heap, accept smallest trial point. This reduces cognitive load more effectively than presenting one long loop.

Common Failure States

• Using neighbours that are not yet accepted in the upwind equation.
• Accepting a point and later changing its value.
• Forgetting the one-neighbour fallback when the two-neighbour quadratic is not causal.
• Allowing zero or negative speed without defining the intended model.
• Confusing graph shortest paths with an Eikonal discretization.
• Extracting paths with a noisy gradient and assuming all errors come from FMM.
• Reporting O(N log N) while using a data structure that performs expensive linear decrease-key searches.

Practice Ladder

• Beginner: compute 1D arrival times by hand.
• Foundation: implement trial/accepted/far states on a small 2D grid.
• Intermediate: derive and unit-test the two-neighbour quadratic update.
• Advanced: use a spatially varying speed field and recover minimum-time paths.
• Professional: compare first-order FMM, higher-order variants and alternative Eikonal solvers using accuracy, heap work, runtime and path quality on analytic and irregular test cases.

Learning Hall Boundary

This article owns the Fast Marching Method as a causal numerical solver for Eikonal arrival-time problems. It does not replace Dijkstra/A* pathfinding, Jump Point Search, level-set methods, numerical ODE solvers or general PDE instruction.

Evidence Boundary

James A. Sethian’s 1996 PNAS paper introduced a fast marching level-set method for monotonically advancing fronts, and his 1999 SIAM Review article develops the numerical theory and O(N log N) framework in depth. Current scikit-fmm documentation implements the method for Eikonal boundary-value problems.

Professional rule: you understand Fast Marching when you can derive the local upwind update, explain why the smallest trial value can be frozen, and identify the model assumptions that make the one-pass causal ordering valid.