Optimal transport

Particles that never collide

16,384 particles fly in straight lines from shape to shape. Their paths cross everywhere, yet no two are ever in the same place at the same time. A one-line inequality proves it, and we check every pair before it ships.

Matching

Shared schedule

Speed1.00×

Scrub the cycle0%

What you're watching

Straight lines, one clock, no crashes

Each particle is handed a target in the next shape: a sphere, then a spiral galaxy, a trefoil knot, and the OnComp power ring. The GPU moves every particle along the straight line to its target on one shared clock. The only intelligence is in who gets which target, and that is decided offline.

Switch the matching to Random and watch the difference: particles stream through one another and through the middle of the shape. On the certified matching, flights are short and orderly. The readout shows how many pairs would rather swap targets: zero for the certified plan, about half of all pairs for a random one.

How it works

Why nothing crashes

Pick a level on the stage: Curious for the idea in plain words, Builder for the code-level picture, or Mathematician for the statements. The pictures are the same at every level.

1 / 8

The question
Twenty-two dots fly from a big ring to a smaller, turned one. Each travels in a straight line, and they all set off and arrive together.
Look at the paths: they cross everywhere. Yet no two dots ever bump. Watch the highlighted crossing: one dot goes through it early, the other much later. Why does it always work out?
The stakes
Hand the targets out badly and it goes wrong. These two dots each head for the far corner. Halfway through, they reach the centre at the same moment. That’s a crash.
With thousands of dots and a careless plan, crashes like this are everywhere.
The score
Give every plan a score: add up how far each dot travels, but square each distance first. The squares on the paths show it literally, since a square’s area is its side squared.
Now scroll, and the two targets swap. Both trips get shorter, the squares shrink, and the score drops.
No swap helps
Start from a random plan and keep making any swap that lowers the score. Every swap makes it strictly lower, so this can’t go on forever. It stops when no single swap would help.
Scroll and watch the number of helpful swaps fall to zero.
Any timing
The clock doesn’t have to tick evenly. Dots can start slowly and finish fast, or even drift backwards for a moment. What matters is that they all share the same clock and it stays between start and finish.
On a stable plan, the crash count stays at zero whatever the timing.
Why it works
Suppose two dots on a stable plan did crash. Freeze them at the moment they meet.
Draw an arrow between their two starting points, and another between their two targets. At a crash, these arrows always point in exactly opposite directions. Opposite arrows are precisely the situation where swapping the targets lowers the score.
But on a stable plan, no swap lowers the score. So a stable plan can never crash. That’s the whole proof.
Why squared
Why square the distances? Put two dots on a line at 0 and 1, with targets at 2 and 3. Plan A sends 0 to 3 and 1 to 2; plan B sends 0 to 2 and 1 to 3.
Add plain distances and the plans tie: 4 each. Yet plan A’s dots meet at 1.5. Squaring breaks the tie, 10 against 8, so the plan that crashes never wins.
The theorem
So the rule is simple: pick a plan where no swap helps, and the dots can fly in straight lines without ever meeting.
The live demo at the top runs this with 16,384 particles, and every pair in every flight is checked before it ships.

The theorem

Swap-stable plans fly collision-free

Let $x_1, \dots, x_n$ be distinct points of $\mathbb{R}^m$ , let $y_1, \dots, y_n$ be distinct points of $\mathbb{R}^m$ , and let $\sigma$ be a permutation that is swap-stable: for every pair $i \neq j$ ,

\begin{aligned} &\lvert x_i - y_{\sigma(i)}\rvert^2 + \lvert x_j - y_{\sigma(j)}\rvert^2 \\ &\quad \le \lvert x_i - y_{\sigma(j)}\rvert^2 + \lvert x_j - y_{\sigma(i)}\rvert^2, \end{aligned}

equivalently $(x_i - x_j)\cdot(y_{\sigma(i)} - y_{\sigma(j)}) \ge 0$ . Put $p_i(s) = (1-s)\,x_i + s\,y_{\sigma(i)}$ . Then for any $\varphi : [0,T] \to [0,1]$ and every $t$ , the points $p_1(\varphi(t)), \dots, p_n(\varphi(t))$ are pairwise distinct.

Read the proof

It suffices to show that for each $s \in [0,1]$ the points $p_i(s)$ are pairwise distinct, since every particle uses the same $s = \varphi(t)$ . At $s=0$ they are the $x_i$ , and at $s=1$ the $y_{\sigma(i)}$ ; both families are distinct.

Let $0<s<1$ and suppose $p_i(s) = p_j(s) =: z$ for some $i\neq j$ . Write $d_i = y_{\sigma(i)} - x_i$ and $d_j = y_{\sigma(j)} - x_j$ . Then

\begin{aligned} x_i &= z - s\,d_i, \\ x_j &= z - s\,d_j, \\ y_{\sigma(i)} &= z + (1-s)\,d_i, \\ y_{\sigma(j)} &= z + (1-s)\,d_j. \end{aligned}

so $x_i - y_{\sigma(j)} = -s\,d_i - (1-s)\,d_j$ and $x_j - y_{\sigma(i)} = -s\,d_j - (1-s)\,d_i$ . Expanding,

\begin{aligned} &\lvert x_i - y_{\sigma(j)}\rvert^2 + \lvert x_j - y_{\sigma(i)}\rvert^2 \\ &= \big(s^2 + (1-s)^2\big)\big(\lvert d_i\rvert^2 + \lvert d_j\rvert^2\big) \\ &\quad + 4s(1-s)\,d_i\cdot d_j, \end{aligned}

while the current cost of the pair is $\lvert d_i\rvert^2 + \lvert d_j\rvert^2$ . Since $s^2 + (1-s)^2 - 1 = -2s(1-s)$ ,

\begin{aligned} &[\text{swapped}] - [\text{current}] \\ &\quad = -2s(1-s)\,\lvert d_i - d_j\rvert^2. \end{aligned}

Swap-stability says this is $\ge 0$ . As $0<s<1$ , that forces $d_i = d_j$ , and then $x_i = z - s\,d_i = z - s\,d_j = x_j$ , contradicting distinctness. $\blacksquare$

The same proof in one line

Expanding the four squares shows $[\text{swapped}] - [\text{current}] = 2\,\Delta x\cdot\Delta y$ with $\Delta x = x_i - x_j$ and $\Delta y = y_{\sigma(i)} - y_{\sigma(j)}$ , so swap-stability is $\Delta x\cdot\Delta y \ge 0$ . Then

\begin{aligned} &\lvert p_i(s) - p_j(s)\rvert^2 \\ &\quad = (1-s)^2\lvert\Delta x\rvert^2 + s^2\lvert\Delta y\rvert^2 \\ &\qquad + 2s(1-s)\,\Delta x\cdot\Delta y > 0, \end{aligned}

because the last term is non-negative, $\Delta x \neq 0$ , and $\Delta y \neq 0$ .

Why the hypothesis is the right one

The proof only uses swap-stability for the one pair that would collide. So a matching built by any heuristic is collision-free as soon as no single exchange lowers the total squared distance. A full optimum is not required, which is what makes the certificate cheap enough to compute for every pair.

Adversarially reviewed by four independent AI verifiers; all four found no hole. Every pair in the shipped matchings is certified offline.

The certificate

Every pair, every flight

Each shape is sampled once and rounded to the int16 coordinates the GPU receives. A first matching comes from recursive bisection: split both shapes at the median of their principal axis and match halves, the way sorting solves the problem in one dimension. Pairwise swaps then repair it until the check passes for every pair. The check runs on the integers themselves, where double-precision arithmetic is exact, so the certificate holds for exactly the data that ships.

Flight (16,384 particles)	Pairs checked	Closest approach	Random plan: would swap · closest
Sphere → Galaxy	134,209,536	0.00061	67,410,859 · 0.000032
Galaxy → Trefoil knot	134,209,536	0.00061	66,541,584 · 0.000017
Trefoil knot → OnComp mark	134,209,536	0.00046	67,083,502 · 0.000044
OnComp mark → Sphere	134,209,536	0.00046	67,317,758 · 0.0000047

Distances are in scene units; each shape is about 2 units across. “Closest approach” is the exact minimum over all pairs and all times, computed in closed form (the squared gap is a quadratic in s). Phones get a separately certified set of 8,192 particles.

Sources

More demos

Fluid dynamics

A vortex that blows up

The swirling core from the September 2026 Navier–Stokes blow-up construction, run on the GPU in its own similarity coordinates.

Numerical methods

One character of code

Two clouds of particles stirred by the same field, two ways. One stays perfectly even forever; the other clumps.

Number theory

The golden angle

Why sunflowers use 137.5°, and the theorem that says points on a circle only ever leave three gap sizes.