A drawn reach set stops at the river

Every reach set ever drawn is too small proves something with a sign in it. An isochrone is drawn by walking out along a finite number of bearings until the budget runs out and joining the points, every vertex of that polygon lies on the true boundary, every edge is a chord, and so the drawn set is inside the true one and short of it by an amount that falls as the square of the count.

The proof has two hypotheses and it names both. The reach set has to be convex, so that a chord between two points of its boundary stays inside. And it has to be star-shaped about its centre, so that walking out along a bearing and stopping at the first place the budget runs out finds the only place it runs out. Everything that essay measures satisfies both, and it says so, and it says what would not: a cost surface with a barrier in it.

A river is the simplest barrier there is.

The set, exactly #

Nothing in that figure is sampled on a grid, and the reason it does not have to be is worth a paragraph, because it is what lets every number below be exact rather than approximate.

On a plane with nothing in the way, the quickest route between two places is a straight line, so the reach set of a walk of ten kilometres is a disc of radius ten kilometres. Put a straight river across it and two things change. A route that must go round prices what an obstacle does to one route; here the obstacle is in the way of every route to the far side at once, and what matters is where it can be passed. The ground short of the river is still reached in straight lines, so it is the disc cut off at the bank. The ground beyond the river can only be reached through a bridge, and once across a bridge the far side is open ground again, so the quickest route to any point there is a straight line to the best bridge, the crossing, and a straight line onward.

That makes the far side a union of half-discs. Each bridge is reached with some of the walk used up — the straight-line distance to its near end, plus the river’s own width to cross it — and whatever is left is the radius of a half-disc centred on its far end. A bridge seven kilometres away along the bank leaves less than three kilometres of walk and a small half-disc; the bridge nearest the centre leaves almost seven and a large one.

So along any bearing from the centre, the reachable ground is a set of stretches with closed-form ends: one running from the centre to the bank or the edge of the disc, and possibly one more starting on the far bank where the bearing passes through some bridge’s half-disc. Every area in this essay is an integral over bearing of the lengths of those stretches, taken in forty thousand steps of bearing, and nothing about it depends on a lattice resolution.

Why the fan stops at the bank #

The instrument whose failure is being measured is the one every isochrone tool uses and every one of the earlier reach essays drew with, and it is worth being precise about what it does.

The walk goes out along the bearing and stops at the first point where the travel time exceeds the budget. On open ground that is the only such point, since the time rises steadily along the bearing and crosses the budget once.

With a river there is a point on the bearing that cannot be reached at any cost — the water — and the walk meets it at the bank. The travel time jumps there from the time to the bank to no finite time at all, so the budget is exceeded, and the walk reports the bank as the edge of the set.

It is not wrong about that. The bank genuinely is a boundary point of the reach set: there is reachable ground on one side of it and unreachable water on the other. What the walk cannot know is that the bearing re-enters reachable ground on the far bank, because it stopped before getting there. The polygon’s vertices are all on the true boundary, exactly as the convex proof requires. They are simply not on the outer boundary, and a polygon through inner boundary points encloses the inner part.

The bearings that do reach the far side are the ones that happen to cross the river on a bridge. With bridges twelve metres wide at intervals of two and a half kilometres, that is about one in two hundred of the bearings that meet the river, and one in 512 of all bearings. A fan of a thousand and twenty-four threads two.

Converged, and short by nearly a third #

The convex proof’s other half is the rate, and it is the rate that turns a coarse drawing into a fine one. It does not survive the river.

At six bearings the river curve is the other curve plus the far side: a hexagon misses 17.3 per cent of a disc whether or not there is a river, and the far bank adds its thirty, for 46.8 in all. As the count rises the chord part falls away exactly as it does without the river, and by about forty-eight bearings nothing is left of it — what remains is the far side, and the river curve goes flat.

That flat stretch is the whole difficulty. The check anybody runs on a drawn reach set is a convergence check: draw it at 72 bearings, again at 144, and see whether the area stops moving. On the river curve it has stopped moving by forty-eight — the drawn area changes by less than one per cent of itself between forty-eight bearings and a thousand — and every convergence check passes. The answer it has converged to leaves out 30 per cent of the reachable ground, and nothing in the sequence of numbers says so.

This is a different kind of error from the one the square law describes, and it is worth stating the difference in the same units. The chord deficit is $O(n^{-2})$: it is a sampling error, and a finer sample removes it. The river deficit is O(1): it is an error in what the walk reports rather than in how many walks there are, and no finer sample touches it. A map with no graticule meets a cousin of this in another field, where a search that recovers a correspondence exactly on clean data fits the noise on real data; in both, the instrument is doing precisely what it was built to do and the thing it was built to do is not the question.

Why the check that passes is the one everybody uses #

A convergence check is the right instrument for the error it was designed for. A fan’s chord deficit falls monotonically and quickly, so watching the area settle as the count doubles is a cheap and reliable way to know the fan is fine enough. The score is not stable at any scale is about a quantity where that check fails loudly — a perimeter that keeps growing — and so the failure is visible.

The river case fails quietly. The area settles, as it should, and the settled value is wrong. That is the worst combination an instrument can have: a diagnostic designed to catch one kind of error returning a clean bill on a result dominated by another kind. A condition imposed at points is not a condition finds the same shape in a solved map, where refining the samples improves the reported residual and leaves the map untouched: in both, refinement explores one axis of the method while the error lives on another.

The miss is the disc’s far segment #

How much is missed depends on where the river is, and the dependence has a closed form that makes the measurement checkable rather than merely plausible.

If every point of the bank were a bridge, the far side would be reached in straight lines, and the reach set would be the whole disc less the strip of water. The share of a disc of radius R beyond a line at distance d is its far segment, $(\arccos\delta - \delta\sqrt{1-\delta^2})/\pi$ with $\delta = d/R$, and that is the most a fan could miss. At three tenths of the walk it is 31.2 per cent; at a tenth, 43.6; at nine tenths, 1.9.

Real bridges fall short of it in two ways, both small. The gaps between bridges leave far-side ground that no half-disc reaches, and crossing the river’s eighty metres uses up eighty metres of walk. Together they bring the far side to 30.3 per cent at three tenths, and the fan misses essentially all of it: its measured miss is the far side plus the chord deficit, to within the few bearings that happen to thread a bridge.

The right-hand end of the figure is the refusal, and it is sharp. With the river further away than the walk reaches, the reach set is exactly the disc, the far segment is exactly zero, and the fan’s miss must be exactly the chord deficit of a seventy-two-sided polygon in a circle, 1 − (72/2π)·sin(2π/72) = 0.127 per cent. It is, to the precision the integral carries, and nothing is claimed beyond the true set. So the barrier case reduces to the convex one exactly when there is no barrier, which is what says the far-side numbers are about the river and not about the integration.

Better crossings, worse drawings #

Every bridge added to the river enlarges the true reach set and leaves the drawn one untouched, so the drawing gets worse exactly as the crossing gets better.

With one bridge within reach, a little east of north, the far side is a single half-disc of nearly seven kilometres’ radius, and the fan misses it. Add bridges and the half-discs multiply and merge; by a bridge every kilometre they cover almost the whole of the far segment, and the fan misses that. Nineteen bridges instead of one raise the far side from a quarter of the reachable ground to 30.7 per cent of a larger total, and add not a square metre to the drawn polygon.

The effect saturates at the far segment, and the approach is fast — by a bridge every two and a half kilometres the far side is within a point of its limit — which is why the measured miss in the closed-form figure sits so close to the dashed curve. A town on a river with the ordinary number of bridges is, for this purpose, a town on a river with continuous crossings.

That is the opposite of the intuition a barrier produces. A river crossable at one place feels like the case where a reach map is most likely to be wrong, because the crossing is so obviously a detour. It is the case where the map is least wrong, because there is least ground beyond the crossing to leave out.

What the partition does beside a river #

The miss is not only an area, and it follows from the construction without a further measurement what it does to a division of ground. Nearest of many is a partition divides ground among several sites by which can reach it soonest, and a partition under a directed cost has two versions shows how much the division moves when the cost changes shape. A division computed by testing which site’s drawn polygon a place falls inside inherits every polygon’s omission.

Two stations on opposite banks make the case concrete. Each one’s polygon stops at its own bank, so any far-bank ground a station can reach across a bridge is in neither polygon, and a division built from polygons leaves it unassigned. Computed from the travel times instead, every such place goes to whichever station reaches it soonest, and the boundary between the two catchments runs down the river except where a bridge lets one station reach further across than the other can reach back. How large those strips are depends on where the stations and the bridges sit, and it is not measured here.

The count that sees it #

The failure is in the walk stopping at the first boundary, so the repair is a walk that does not stop.

Walking each bearing all the way to the edge of the budget costs no more than walking it to the first boundary — it is the same walk, not abandoned early — and it returns every stretch of reachable ground along the bearing rather than the first. A bearing with one stretch is one a fan handles correctly. A bearing with two is a bearing where the fan’s polygon is wrong, and the share of such bearings is a diagnostic that fails loudly exactly where the convergence check fails quietly.

It is not a repair of the polygon, and it cannot be. A reach set that comes in pieces along a bearing is not star-shaped, and a polygon through one point per bearing can only ever draw a star-shaped set. The honest picture of such a set is its outline traced as a contour of the travel time over the whole area — which is what the half-discs in the first figure are — and a fan of bearings is simply the wrong instrument for it, at any count.

What the count supplies is the test for which instrument is needed. Walk the bearings once, count the pieces, and if every bearing has one, draw the fan and trust the square law. If any bearing has two, the fan’s area is an estimate of the near part of the set, and the far part has to be traced another way.

Over-claim, and why there is almost none #

The convex proof also guarantees the polygon never claims ground outside the set, and it is natural to expect a barrier to break that guarantee too. Beside a straight river it barely does.

The ground short of the river is a disc with a straight cut across it, and that shape is convex, so chords between vertices on the bank and the arc stay inside it. It is the same containment the reach set takes the shape of the roads uses as a check on its own lattice, applied to a polygon instead of a hull. The only vertices beyond the river are the rare ones on bearings that thread a bridge, and each of those lies inside the half-disc its own bridge reaches, with the chords to its neighbours running mostly through that same half-disc. The measured over-claim is 0.009 per cent of the reachable ground at a thousand bearings, and it reaches 0.07 per cent only when the bridges are widened to a quarter of a kilometre, so that many more bearings thread them.

That smallness depends on the river being straight. A river that bends towards the centre cuts a non-convex bite out of the near side, and chords across the bend then claim water and far-bank ground that cannot be reached. The size of that over-claim is not measured here, and its rate in the count is not the square law either.

Where the model stops #

The river is straight and the ground is uniform. Walking speed is the same everywhere off the river, and the river is a strip of constant width with no islands, fords or ferries. A ferry is a bridge with a waiting time, and changes the half-discs’ radii without changing the argument.

The bridges are short and perpendicular. Each crossing is charged the river’s width and nothing else, and a bearing counts as threading a bridge only if it meets the near bank within the bridge’s own width. A bridge at an angle, or a long causeway, changes where its half-disc is centred by less than its own length.

The plane is flat. A ten-kilometre walk is far inside the size at which how small is flat enough puts any curvature effect below a millimetre.

And the budget is a single number. The reach set is one level of the travel time. A map that draws several isochrones at once draws several levels of the same function, and each carries the same failure independently: the fan misses the far side of the river at every level the river is within.

Still open: a barrier with a shape #

Everything here is a straight river, and a straight barrier leaves the near side convex, which is why the polygon’s error is all omission and almost no over-claim.

Real barriers bend. A river meanders, a coastline has inlets, a motorway curves, and each one cuts a non-convex bite out of the near side of the reach set as well as hiding a far side behind it. Such a set breaks both of the convex proof’s hypotheses at once: bearings that meet it twice, and chords that cross water. Whether the two errors partly cancel in a drawn area — a polygon short on the far side and long across the bends — or add, and at what rate the over-claim part falls with the count, is the question a straight river cannot ask.