Nearest is a question about the metric

Which of these is nearest is the most-asked spatial question there is, and it is not a question about geometry until a metric is named. A program handed a table of coordinates will use the one its coordinates come with, which is the plane they happen to be stored in, and the plane’s distances are the ground’s multiplied by a factor that varies.

The mechanism, which is not that the plane is inaccurate #

If a projection multiplied every distance by the same factor, no query would ever change answer: a ranking is invariant under a uniform scaling. The plane’s distances are wrong in a way that does not matter at all.

What matters is that the factor varies. Two candidate sites at different bearings and different distances from a query are measured through different parts of the projection, so their apparent distances are scaled differently, and if the true contest is closer than the difference in scaling, the order flips.

That gives a bound rather than a rate: a disagreement can only occur when the two candidates’ true distances are within the region’s own scale spread. The assertion is written as that bound — every disagreement’s margin below the spread — and not as there will be disagreements, because whether a close contest arises is a property of where the points happen to be.

The rates, on four planes over the same ground #

The ordering is the useful part and it is not the ordering of the spreads. Web Mercator is by far the best of the four, with a rate of 1.25 per cent, and it has the second-largest spread.

The reason is conformality. Mercator’s scale factor varies enormously with latitude and is the same in every direction at each point, so two candidates at similar distances from one query are scaled by nearly the same factor whatever their bearings — the local distortion is a magnification rather than a shear. On the plate carrée, which is neither conformal nor equal-area, a north–south candidate and an east–west candidate at 55° north are scaled differently by a factor of 1.7, and the ranking flips whenever the contest is closer than that.

So the property that matters for a distance query is not equal-area and not small distortion, but conformality — which is not the answer anybody would guess from the fact that Mercator is the projection everyone criticises for its distances. Conformal does not mean the angles are right makes the neighbouring point about finite angles; this is the same distinction for finite distances, and here the local property is the one that pays.

The control, which is what makes it a measurement #

Over a box one degree across, at 51° to 52° north, the same procedure gives zero disagreements out of four hundred, with a scale spread of 24,738 parts per million.

That is the control the rest of the essay rests on. A rate on its own could be an artefact of the point set, of the scatter’s construction or of the distance functions. A rate that goes to zero exactly when the projection’s spread falls below the typical margin between neighbours is the mechanism, and it is the reason a city-scale application never encounters any of this and a continental one does.

The scatter itself is deliberately not random: the points come from an additive-recurrence sequence, which gives the same set on every build and spreads without clustering. The essays on datums found a seeded shuffle that turned out to be a shear, and a sequence with no state cannot have that failure.

Where the wrong answer lands #

A rate says how often; a penalty says how much. Over Europe on Web Mercator the five disagreements cost 19.1, 20.2, 24.3 and two smaller distances — so a query that gets the wrong answer gets one about twenty kilometres further away than the right one, out of typical neighbour distances of a few hundred.

Over the whole world, with sixty sites, the rate rises to 26 of 400 and the worst penalty to 1,355 kilometres. The penalty scales with the spacing of the sites rather than with the projection, which is worth separating: the projection decides whether the answer flips, and the data decides how much that costs.

There is also a direction to it. Of the five European disagreements, in all five the planar answer is the site nearer the equator — because Mercator inflates distances by $\sec\varphi$, so a candidate at higher latitude is measured through a more magnified part of the plane and appears further away than it is. A small sample, and a mechanism that predicts the sign in advance.

Why 98.75 per cent is the dangerous number #

A failure rate of one in eighty is the worst possible rate for a defect, and it is worth saying why rather than treating it as reassuring.

At a rate of one in two, the operation is obviously broken and gets fixed on the first day. At a rate of one in a million, nothing downstream depends on the missing case. At one in eighty, every test passes, every spot check passes, and the wrong answers accumulate — and each one, examined individually, looks like a plausible answer to a slightly different question, because the site returned really is nearby.

The same shape has appeared twice already in this field. A datum offset of a hundred metres is dangerous because it is plausible; a scale bar read at the wrong latitude is dangerous because the reading is a number of the right order. The pattern is that the errors that survive are the ones inside the range a reader would accept, and the way to catch them is never inspection — it is a second computation by a different route, which is the site’s whole method turned on the reader’s own work.

The operations that inherit it #

Nearest-neighbour is the simplest member of a family, and every member carries the same dependence.

A distance threshold — everything within so many kilometres — is the same computation with a cut instead of a minimum, and the same flips appear as inclusions and exclusions. That is the version a degree is not a unit of length measures when the threshold is written in degrees, where the region is an ellipse before the projection is even considered.

k-nearest flips more often than nearest, since it has $k$ boundaries to get wrong rather than one.

A Voronoi diagram is the nearest question asked everywhere at once, so its cell boundaries move by exactly the amount that makes the two answers differ. Two diagrams of the same sites, one built in the plane and one on the ellipsoid, differ along their boundaries and agree in their interiors.

And clustering inherits it through whatever distance it is given, which is usually the plane’s.

None of those is a different problem. They are one problem — the metric is an input and the file does not carry one — appearing wherever a distance is compared to another distance.

What it costs to do properly #

Three options, in increasing cost and accuracy.

Project to something local. An azimuthal equidistant projection centred on the query has true distances along every ray from its centre, which is exactly what a nearest-neighbour query needs. It costs a projection per query and it is exact for the operation, which is the clean answer nobody uses because it means reprojecting the candidate set for every question.

Use the plane to filter and the ellipsoid to decide. Take the planar $k$ nearest, then rank those properly. The filter’s error is bounded by the spread, so a $k$ large enough to absorb it makes the answer exact — and the required $k$ is computable from the spread, which is the useful form of the bound this essay measures.

Compute everything on the ellipsoid. Vincenty per candidate, which is an iteration rather than a formula: geodesics on the ellipsoid sets out why there is no closed form, and the cost is why nobody does this for a large candidate set without filtering first.

The middle one is the answer, and it is the shape of most correct spatial computation: an approximation with a bound, followed by an exact test on what the bound admits.

The same question with a line instead of a point #

A nearest-neighbour query compares distances from a point. The corridor version compares distortion along a route, and it is the one case in this collection where the objective is a curve rather than a region — which changes the answer.

Choosing for a line, not a region measures it: the projection that minimises distortion over an area is not the one that minimises it along a path through that area, and that essay found the comparison had to be made in parts per million rather than as a ratio of spreads, because a ratio of numbers near one flattered a loser sevenfold.

The connection to this essay is direct. A query’s accuracy depends on the scale spread over the region containing the query and its candidates — a disc, not the whole dataset’s extent — so the right plane for a query is the one that minimises the spread over that disc. For a dataset covering a continent and queries that are always local, the correct answer is a different plane for each query, which is the azimuthal-equidistant option above and is why it is exact.

The practical compromise is a plane chosen for the region and a filter wide enough to absorb its spread. Both halves are computable, and the field’s recurring instruction — name the operation, then choose the plane — is here a formula rather than an aphorism.

The bound had to be measured properly, and the first version was not #

One thing in this essay’s machinery was wrong when written, and it is the kind of wrong worth recording.

The spread was first sampled on a 9 × 9 grid over the region. On an azimuthal projection centred far from the region, that sample missed the extremes — which sit in the corners — and reported 20 per cent where the true spread is 58. The bound then failed: a measured margin of 29 per cent against a spread of 20, which reads as a refutation of the claim.

Nothing was wrong with the claim. A coarse sample of a supremum is not a supremum, and an assertion resting on one is asserting the sampling. At 41 × 41 the same projection reports 58 per cent, the bound holds on all six projections tested, and the check is now about the geometry rather than about the grid.

That is the third time here that an assertion had to be rewritten to say what was actually being measured, and each time the repaired version is the stronger claim.

What a geodesic costs, and why the filter is not laziness #

The exact answer needs an inverse geodesic per candidate, and it is worth being concrete about what that is, because “just compute it properly” hides an iteration.

Vincenty’s method solves for the distance between two points on the ellipsoid by fixed-point iteration, typically three or four passes of a dozen transcendental functions each. Against a planar distance — two subtractions, two multiplications and a square root — it is two orders of magnitude more work, and it does not always converge: near-antipodal pairs are the failure case, mapped rather than warned about in the route with no shortest path, and this collection found that its convergence flag could be true beside a NaN because the loop’s exit test is a comparison and NaN fails every comparison.

So a candidate set of ten thousand, queried a million times, is not a place for an unfiltered exact computation, and the filter-then-decide structure is engineering rather than compromise. What makes it correct engineering rather than an approximation is that the filter’s error is bounded: everything the plane could have mis-ranked is inside the spread, so a $k$ chosen from the spread admits every possible winner.

That is the same shape as the site’s other bounded approximations — the Simpson integration of a line’s scale factor, whose fourth-order convergence is asserted rather than assumed, and the meridian arc’s series checked against an independent quadrature. An approximation with a measured bound is a method; an approximation without one is a hope.

What the field says here #

The answer to which is nearest is not in the data. It is in the data plus a metric, and the file supplies the first and a program supplies the second by default, silently, from whatever plane happens to be in use.

That is the whole of the operation decides the coordinate system in one operation, and this one is the sharpest case because the output is not a number that could be corrected afterwards — it is an identity, a different site, and no post-hoc scaling recovers it.

A one-sided test that costs one extra run #

The defect’s worst property is the one named above: the output is an identity, so nothing about it looks wrong. But that does not make it undetectable, and the test is cheap enough that there is no excuse for not having run it.

Compute the answer twice, in two different planes, and compare the identities. Any query where the two disagree is a proven error — the two planes rank the candidates differently, at most one ranking can match the ground, so at least one of the two runs is wrong about that query. No ground truth is needed to establish it, which is what makes the test practical on a dataset nobody has a reference answer for.

The test is one-sided, and this collection’s habit is to say so plainly. Disagreement proves an error; agreement proves nothing, because two planes distorting the same neighbourhood in the same direction will happily agree on the same wrong site. What agreement gives is a lower bound on the exposure rather than a clean bill.

The cost is one extra pass, which is a factor of two — against the exact geodesic computation’s much larger factor, and against the filter-then-decide structure’s requirement that somebody derive and defend a bound. Doubling a query that already runs is the cheapest diagnostic available here.

And the disagreement rate is itself the measurement worth having. Only the near-ties can flip, so the fraction of queries on which two planes differ is a direct estimate of how close this particular dataset runs to the boundary — a property of the candidate spacing and the query distribution rather than of the projections. A dataset whose two runs agree on every query has candidates far enough apart that the metric never mattered, and the right response is to stop worrying about it rather than to buy the exact computation.

There is one caveat, and it is about how the two planes are picked. Two projections from the same family — two UTM zones, two conic variants with nearby standard parallels — distort a small neighbourhood in nearly the same way, so they will agree far more often than two unrelated planes and will understate the exposure. Choosing a conformal plane against an equal-area one gives the test something to find.

That is the shape the whole field keeps producing: not use the expensive method, but measure whether the cheap one is exposed here, and let the answer decide. The two planes need not be well chosen; they need only be different, because the test is about whether the ranking is stable rather than about which plane is right.

Where this ladder goes #

The last two operations are the ones where the object being computed is not a number or an identity but a picture: reprojecting a raster, which invents values it does not have, and then the table that collects every operation in this field with the plane that makes it exact.