Points arrive one at a time in the plane, each with a weight. You want to match them into pairs to maximize total weight, subject to one geometric constraint: the line segments connecting matched pairs cannot cross. You must decide, as each point arrives, whether and how to match it. The matched pairs' segments must form a non-crossing configuration — a planar matching.
The question is how well an online algorithm can compete with the best offline solution, which sees all points before deciding.
For deterministic algorithms with arbitrary weights, the answer is: not at all. No deterministic algorithm can achieve any finite competitive ratio. An adversary can exploit the algorithm's predictability to construct point sequences where the algorithm is forced into a geometric configuration that blocks all future high-weight matches. The non-crossing constraint means a single bad segment can partition the plane, making large regions of it unreachable. A deterministic algorithm's choices are predictable, so the adversary places the valuable points in the blocked regions.
Randomized algorithms, by contrast, achieve a constant competitive ratio. The randomness prevents the adversary from knowing which regions will be blocked, so it cannot reliably place high-weight points in the dead zones.
The sharpest result is about revocability. Give the deterministic algorithm the power to undo its matches — to unmatch a pair and rematch the freed points elsewhere. This is a strictly stronger model. The algorithm can correct its own mistakes. And it still can't achieve a non-trivial competitive ratio.
This means the bottleneck is not commitment. The problem is not that the algorithm makes irrevocable decisions too early. Revocable decisions are equally useless. The problem is that the algorithm makes predictable decisions — whether revocable or not. The adversary doesn't exploit the algorithm's permanence; it exploits its transparency. Every deterministic response to every possible input is computable in advance, and the adversary uses that computability to engineer geometric traps that no sequence of corrections can escape.
Randomization doesn't give the algorithm better judgment. It gives it unpredictability. The matched segments still block future matches; the algorithm still commits to configurations it might regret. But the adversary can no longer know which configurations will emerge, so it can no longer place the high-weight points in the dead zones.
The undo is useless because the problem was never about mistakes. It was about legibility. A coin flip solves what foresight cannot.
"On the Online Weighted Non-Crossing Matching Problem," arXiv:2603.09262 (March 2026).