A partition under a directed cost has two versions

Nearest of many is a partition divides a surface among several sites: every place belongs to whichever site is nearest, the division is a set of curves, and computing it in the plane the data is stored in hands away up to 22 per cent of the ground.

Every word of that rests on a distance, and a distance is symmetric. How far London is from Madrid and how far Madrid is from London are the same number, so “the site nearest to this place” and “the place nearest to this site” are the same question and there is one division.

The set that can be reached is not the set that can reach shows what happens when the cost stops being symmetric. Under a flow at 45 per cent of a vehicle’s own speed, the set a place can reach and the set that can reach it have the same area to five significant figures and share only 32 per cent of their union.

Put the two together and a partition acquires two versions.

The two divisions are different questions #

Which of the two a person wants is decided entirely by what the sites are, and the split is clean.

Outbound is what a supplier wants. A lifeboat station, a fire service, an air ambulance, a delivery depot: the question is which base can get to this place fastest, and the cost is the base’s travel time to the place.

Inbound is what a destination wants. A hospital catchment, a market’s hinterland, an airport’s drawing area, an evacuation plan: the question is which site this place can get to fastest, and the cost is the place’s travel time to the site.

Under a symmetric cost the two produce one map and nobody has to choose. Under a flow they produce two, and a planner who computes one and uses it for the other has assigned half the ground wrongly.

The word “catchment” carries the confusion in it. A hospital catchment is inbound — patients travel to the hospital — and an ambulance catchment is outbound, and they are frequently drawn as the same polygon.

The same object, one field over #

The two divisions are the same construction the maritime field has been drawing for a century without noticing there could be two.

An equidistance line belongs to a surface traces the boundary between two coasts as the set of places equidistant from both, which is a Voronoi boundary with two sources, and finds that the surface the distances are computed on moves it by up to 39.6 kilometres. That whole rung uses a distance, so the question of direction does not arise — a delimitation is about ownership rather than about travel, and ownership has no direction in it.

The moment the cost is a travel time, it does. A fishing ground assigned by which port can reach it soonest and one assigned by which port a boat there can run to soonest are different grounds, and under any prevailing wind or current they are substantially different. Nothing in maritime delimitation is drawn that way, and nothing in this essay says it should be; what the measurement supplies is the size of the difference between the two questions, in case anybody wants to ask the second.

What changes and what does not #

The headline number invites a second one that turns out to be far smaller, and the gap between them is the finding.

So half the world changes hands and nobody’s holding changes much. That combination is worth stating carefully because it is easy to read as a contradiction and is not one.

A partition boundary between two sites is where their two costs are equal. Introduce a flow and both costs change, so the boundary moves — but it moves along itself as much as across itself, and the ground it sweeps on one side of a site is compensated by ground it sweeps on the other. The site’s total is nearly conserved and its shape is not.

Which means a planner comparing the two divisions on a summary statistic would see nothing. The share of the world each site holds is almost the same number under both, and every quantity computed from those shares — a workload, a population, a total demand — comes out nearly identical. The difference is entirely in which places, and only a map shows it.

How the disagreement grows with the flow #

The flow strength in the figures above is one number and there is no reason to think it is the important one.

The disagreement is nearly linear in the flow’s strength at low strength — 12.4, 24.3 and 35.5 per cent at 0.1, 0.2 and 0.3, which is a slope of about 1.2 per unit — and bends over as it approaches complete disagreement. That linearity is the useful part: a flow at a tenth of the vehicle’s speed, which sounds negligible, already moves an eighth of the sphere between the two divisions.

A tenth is not a hypothetical strength. A jet stream against a subsonic aircraft, a tidal stream against a small vessel, a gradient against a cyclist and a one-way system against a delivery van are all in that range or well above it, and every one of them is a cost with a direction in it.

The zero at zero flow is the check the rest depends on. With no flow the cost is a distance, the two divisions are one division, and any disagreement at all would be the two grids being walked differently rather than the ground being divided differently. It comes out at nil rather than at a small number, and the assertion on this file requires it.

The boundary between two sites, and why it moves along itself #

The mechanism behind the small holding changes deserves a picture in words, because it is what makes the whole result counter-intuitive.

Under a symmetric cost the boundary between two sites is the perpendicular bisector of the line joining them — a curve at right angles to that line, crossing it at the midpoint. Under a flow, the outbound boundary tilts one way and the inbound boundary tilts the other, and both still pass near the midpoint because a place equidistant in time from two sites in a uniform flow is still near the middle of them.

So the two boundaries cross near the middle and diverge towards the ends, scissoring open. The ground each takes from the other is a pair of wedges on opposite sides, and the wedges have nearly equal area — one on each side of the crossing — so a site gains at one end of a boundary exactly what it loses at the other.

Multiply that over every pair of neighbouring sites and the totals barely move while the map is rearranged. It is the same shape nearest of many is a partition finds for a planar Voronoi division, where the misassigned ground arrives as unbroken strips along boundaries rather than as scatter — and for the same reason: an error in a boundary is an error along a curve, and a curve is where the area is.

Strength is not what decides it #

The three flows this collection carries differ in kind as well as in strength, and the kinds do not order the way the strengths do.

The jet in this library is a band twelve degrees wide about the forty-fifth parallel and the gyre is a circulation twenty degrees across; between them they touch a small fraction of the sphere, and outside it the two divisions agree exactly. The steady westerly is everywhere.

That is a statement about the support of the flow rather than about its magnitude, and it inverts the intuition a strength figure produces. A planner asking whether direction matters for their catchments should ask how much of their region has a directional cost in it, not how strong the strongest one is.

It also says which regions are safe. A place where the cost is symmetric belongs to the same site under both divisions, whatever is happening elsewhere — so a boundary drawn through still ground is a boundary both questions agree on, and only the boundaries running through moving ground are ambiguous.

A set where the disagreement is much worse #

Seven places spread across the world is a set whose sites are far apart relative to how far a flow can push a boundary. Sites close together are a different case.

Two things are different about that set and both matter. The sites are clustered, so most of the sphere is a long way from all of them and its assignment is decided by small differences between large travel times — which is exactly the regime a flow perturbs most. And they are strung out east to west, along the flow, so the flow’s effect on the pairwise boundaries is at its largest rather than at its smallest.

The world set’s sites are spread over every continent and in every direction relative to the wind, so the flow helps some pairs and hinders others and much of it averages out of the holdings. The nordic set has no such averaging available.

Which gives the design rule this rung is for, and it is about the geometry of the sites rather than about the flow: a set of sites arranged ALONG the prevailing direction has two divisions that disagree about their totals as well as about their ground, and a set arranged across it does not.

What a planner does with two maps #

The practical question is what to do when the two divisions are both correct and different, and there is no general answer. What there is, is a short list of the positions.

Pick the one that matches the purpose. Ambulances outbound, hospitals inbound. This is right and is what almost nobody does, because the software that draws catchments computes a distance and a distance has no direction.

Take the intersection and leave the rest unassigned. The ground both divisions give to the same site is unambiguous — 49.3 per cent of the sphere in the case above — and the rest is genuinely contested. That is honest and it is not a partition.

Take a round trip. Assign a place to the site minimising the time out plus the time back, which is symmetric by construction and is a third division that agrees with neither. It is the right answer for a vehicle that must return to base, which is most of them.

The third is the interesting one because it is a real operational question rather than a compromise, and this rung does not measure it. A round-trip cost is symmetric in the sense that matters — the cost from A to B equals the cost from B to A — so it produces one division, and how far that division sits from either of the two here is a quantity nothing in this anchor computes.

Three divisions, and the one nobody draws #

Naming the third division properly is worth a paragraph, because it is the one most real operations actually need and it has no name in the literature.

A vehicle based at a site and returning to it pays the outbound time plus the inbound time. That total is symmetric between a place and a site — the round trip from London to a place and back costs the same as the round trip from the place to London and back, since it is the same two legs — so it produces exactly one division, like a distance does.

But it is not the distance division. Under a flow, a place downwind of a site is quick to reach and slow to return from, and the round trip costs about the same as one to a place at the same distance upwind; the two effects cancel to first order and not to second, so the round-trip division is close to the still-air one and not equal to it. The quickest route is not the shortest measures exactly that cancellation for a single journey and finds the return leg taking four times as long as the outward one at this flow strength.

So there are three divisions of the same ground by the same sites: outbound, inbound, and round trip. Two of them are the subject of this rung and the third is not measured here. One thing about it does follow without measurement: wherever the two divisions AGREE, the round trip agrees with them, because a site that minimises both terms of a sum minimises the sum. So the round-trip division differs from the other two only inside the contested 50.7 per cent, and the 49.3 per cent all three agree about is settled for every one of the three questions at once. Where inside the contested ground it falls is not settled by that argument and is not measured here.

The instrument, and the grid it runs on #

Every number here comes from Dijkstra on a grid of 360 by 181 nodes with eight neighbours each, with the step cost being the ground length divided by the speed made good along it, and with the flow’s sign reversed for the inbound field.

Two things about that are worth stating rather than assuming.

The grid quantises the boundary. Two grids over the same ground is the essay about what happens when one region is covered by two discretisations that disagree; here there is one grid and its own resolution is the limit.

The boundary is a curve and the grid finds it to within a cell, which at this resolution is a degree — about 111 kilometres at the equator. That is coarse against a boundary and fine against a 50 per cent share, and the disagreement share is stable to a tenth of a point between the 240 × 121 grid the ladder uses and the 360 × 181 grid the maps use.

Reversing the flow is not the same as reversing the path. The inbound field is computed by running the same Dijkstra with the flow’s sign flipped, which gives the time to get to the site from every place; the alternative — running the outbound solver from every place — is the same answer computed a hundred thousand times over. The equivalence is exact for a first-order Zermelo cost and it is the reason the figure is computable at all.

The Zermelo cost itself is a first-order approximation, exact while the flow is slower than the vehicle, which every flow here is.

What this does to the pages #

Everything so far is on the ground, and this anchor exists because a reach set drawn on a page is not the reach set. Both divisions here are computed on the sphere, so the page has not entered — and it enters twice over the moment either is drawn.

Nearest of many is a partition measures what computing a division in the plane costs: between 0.75 and 22.16 per cent of the ground misassigned, in unbroken strips up to 1,591 kilometres across, depending on the projection and the region. That error applies to each of the two divisions here separately, and it is not the same error for both — the page distorts the outbound boundary and the inbound boundary by different amounts, because they run in different directions and a page’s distortion has a direction.

So a planner working on a chart faces three errors rather than one: the wrong division for their question, the page’s distortion of it, and the page’s differential distortion between the two. The first is the largest by a wide margin — 50.7 per cent against 22.16 — which is the useful ordering and is the reason this rung is worth having before any question about projections arises.

It is also a case where the ordinary advice inverts. The usual counsel in this collection is to compute on the ground and draw on the page, which fixes the second error and says nothing about the first. Here computing on the ground with the wrong direction is worse than computing on a bad page with the right one.

Where the ladder stops: ground that is not uniform #

Nine rungs have built reach sets out of a distance, a cost, a direction and a competition, and measured what a page does to each. The last two have measured what the instrument does — a finite fan of bearings, a grid of nodes — rather than what the page does.

What none of them has is a reach set on ground that is not uniform. Every cost here is a property of the vehicle and the medium and of nothing else; the surface is featureless, and a place is as easy to cross as any other place. Real reach is decided by roads, by terrain, by borders and by where the ferry runs, and those are a cost field with structure in it rather than a flow.