The turnpike problem asks you to reconstruct a set of points on a line from their pairwise distances, given in scrambled order. It is the inverse of a trivially easy forward problem — computing all pairwise distances from known positions takes quadratic time. Undoing that computation, recovering positions from distances, is combinatorially explosive.
Katz and Rote (arXiv:2603.18283) address the realistic version: what happens when the distances are noisy? Measured with finite precision, rounded, corrupted by instrument error. The standard approach treats noise as a perturbation to be minimized — fit the closest consistent point set. The authors do something different. They exploit triangle equalities.
Any three points define three pairwise distances, and the triangle inequality constrains their relationships. But for collinear points, the constraint tightens to equality: one distance equals the sum of the other two. The authors formulate an integer linear program that finds a consistent labeling of distances satisfying all triangle equalities simultaneously. The key result: under bounded noise followed by rounding, the combinatorial structure — which triples satisfy which equalities — can be recovered exactly, even though the individual measurements are inexact.
This separates the problem into two phases. First, recover the combinatorial skeleton (which distances go together). Second, estimate the actual coordinates by regression. The noise disrupts the numbers but not the relationships between them.
The structural insight matters beyond this particular problem. In many inverse problems, practitioners treat noise as corrupting the answer. Here, noise corrupts the data but preserves the topology of the solution. The skeleton of consistent relationships is more robust than any individual measurement. You don't need exact distances to know which distances belong together. The structure is the signal; the numbers are the noise.