A tolerance is a promise about the picture

Douglas–Peucker makes a promise, and it keeps it. Take the first and last vertex of a run, find the vertex furthest from the chord between them, split there if that distance exceeds ε and recurse; every vertex that survives to be discarded is therefore within ε of the segment that replaced it. That is a theorem about the algorithm and it holds in every measurement below, to the last decimal place.

The trouble is what the promise is about. It is about vertices and a line — a statement in the units the coordinates happened to be in, concerning how far the drawn shape moved. Almost nothing a stored geometry is asked for is that, and the collection has already found the same gap in a centroid that belongs to a plane rather than to a region.

The one thing that does follow #

Before the failures, the one derived quantity that inherits a guarantee, because it is the exception that makes the rest surprising.

The perimeter can only fall. A simplified polyline is a subsequence of the original’s vertices, and by the triangle inequality the path through fewer of them is no longer than the path through all of them. This is not a measurement, it is a two-line proof, and it holds for any algorithm that only ever discards vertices — Douglas–Peucker, Visvalingam, a fixed-stride decimation, anything.

So a generalised coastline is shorter than the one it came from, always, and by an amount that grows monotonically with the tolerance. That is exactly the relation the ruler measurement of the previous rung is about, arriving from the algorithmic side rather than the geometric one: generalisation is a coarse ruler, and a coarse ruler measures less. The tolerance is the stride, and it is not the same ground distance everywhere.

The area drains, or fills, and there is no telling which #

The intuition about area is that a simplification cuts corners, so it loses a bit. For a convex outline that is right and it is a theorem for the same reason as the perimeter: every chord of a convex boundary lies inside it, so every replacement removes area and never adds any. The circle in the figure loses 0.16, 0.64, 2.55 and 9.97 per cent as the tolerance rises through four steps.

For any other outline it is wrong. A boundary with a bay in it has chords that bridge the bay and add area, and chords that cut a headland and remove it, and which of the two dominates at a given tolerance depends on which features happen to fall below it. The measured sequence on the wavy outline is −0.04, +0.11, −0.12, −0.26, +0.38, −1.92, +5.43 per cent. It changes sign four times.

That means there is no correction. A bias with a known sign can be compensated; a national land-cover total generalised at a known tolerance could be scaled back up. A quantity whose sign is not known in advance cannot be, and the only honest handling is to compute areas from the ungeneralised geometry and carry them alongside — which is what a well-built dataset does and what a re-generalised copy of one loses. It is the same discipline that keeps a published coordinate beside the observations it came out of.

Which side of the line a point is on #

Containment is the query a boundary file most often exists to answer. Is this address in this district; is this reading inside this reserve; which of these polygons does this point belong to. Each of those is a claim about the edges before it is a claim about the point.

The counts across the ladder are 6, 7, 13, 17, 51, 63 and 193 of 3,600 — up to 5.4 per cent of the probed area at the coarsest tolerance. The furthest a flipped point sat from the original boundary was 0.075, against a tolerance of 0.128: inside the promise, as it must be, since the boundary cannot move further than ε.

That is the honest statement and it is worth being precise about, because the dramatic version — a point far from the boundary changes district — is false for this algorithm. The true statement is duller and worse:

Every point within ε of a boundary has an answer that the simplification may have decided for it, and ε is chosen to be invisible at the display scale. At 1:1,000,000 a tolerance of a fifth of a millimetre on the page is 200 m on the ground — and the scale on a screen map is not one number, so on a tiled map it is 200 m in one place and rather less in another. The number of addresses within 200 m of a district boundary is not small, and nothing in the file marks them.

One in seven of the band actually flips #

The flip counts are described as entirely predictable in aggregate, and the prediction can be made and checked, which turns a reassurance into a constant worth carrying.

Every flipped point lies within ε of the original boundary, so the affected region is a band of width 2ε along a perimeter P. On a probe grid over a box of area A the expected number of probes in the band is 3,600 × 2Pε/A, which for this outline — perimeter about 6.3 in a box of area 4 — gives 91 probes at ε = 0.008, 363 at 0.032 and 1,451 at 0.128.

Against measured flips of 13, 51 and 193, the realised rate inside the band is 14.3, 14.0 and 13.3 per cent — one in seven, constant to within a point across a sixteenfold range of tolerance.

That constant is the interesting quantity and it has a mechanism. A point flips only if it lies between the two curves, and the simplified boundary crosses the original repeatedly — inside on the chords that cut a headland, outside on those that bridge a bay. Most of the band is therefore on the same side of both curves and only the lens-shaped regions between successive crossings contain flippable points. The one-in-seven figure is the area of those lenses as a fraction of the band, and it is stable because the crossing frequency is set by the outline’s own detail rather than by the tolerance.

So the practical estimate is a seventh of the naive one. A pipeline owner wanting to know how many address queries a generalisation put at risk should compute P × 2ε × the query density and divide by seven — and the naive figure, which is what a cautious estimate would use, over-states the exposure by that factor.

Two cautions go with the constant. It belongs to this outline: a boundary with more detail crosses its own simplification more often and would give a smaller fraction, and a nearly convex one would give a much larger one, up towards the whole band. And it is a fraction of area, not of queries — real query points cluster near boundaries, which is the essay’s own last limit, so the fraction of affected queries is higher than one in seven by an amount nothing here measures.

What survives both cautions is the shape of the estimate: the exposure is proportional to perimeter times tolerance, with a coefficient below one that is a property of the boundary’s own roughness. That coefficient is measurable on any real layer in one pass, at the moment the simplification is run, and it is the number a metadata field ought to carry beside the tolerance.

The curve crosses itself #

The failure with the sharpest edge is topological, and it is the one that turns a data problem into a crash.

The mechanism is a one-liner. The algorithm replaces an arc with its chord as soon as the arc’s own sagitta drops below ε, and the chord cuts inwards by about ε. If another part of the curve is nearer than that, the chord crosses it. The threshold was between 1.5 and 2.2 times the gap on every spiral tried, across three separations and three lengths.

A self-intersecting ring is not merely inaccurate. It has no well-defined interior, so the shoelace formula returns a difference of two areas rather than an area; point-in-polygon returns a parity rather than a membership; and most geometry libraries raise an error or, worse, do not. A river that crosses its own bank and an administrative boundary that ties itself in a knot are the same event, and both break the nearest-feature query that reads them, and both arrive from a tolerance chosen for how the map looks.

What the promise would have to say instead #

It is worth writing down what a useful guarantee would look like, because the gap between it and the real one is the whole essay.

A tolerance that meant something for a stored geometry would bound the Hausdorff distance between the two curves, in both directions, in ground units. That is a stronger statement than Douglas–Peucker’s, and it is stronger in exactly the direction that matters: it constrains where the new line goes as well as where the old vertices were, so it excludes the chord that bridges a bay and the chord that cuts across a neighbouring turn.

Even that bound would not deliver the area or the containment answers. It would deliver a bound on the symmetric difference of the two regions — at most perimeter × ε — which is the aggregate statement the flip counts above obey, and which is genuinely useful for a total. It would still say nothing about any individual point.

And it would still not deliver simplicity. A curve within ε of a simple curve can cross itself: simplicity is not a continuous property of a curve, so no metric bound implies it. Preserving it takes a check, run against the rest of the geometry, at a cost that is why the plain algorithm does not include one.

Three different guarantees, three different costs, and one word — tolerance — used for all of them in the interfaces that offer them.

What was computed, and how #

The outline is a closed curve with detail on it — a circle modulated by two harmonics — at 3,001 vertices, so that a tolerance a hundredth of its radius still has thousands of decisions to make. The probes are a 60 × 60 grid over its bounding box. The spiral is Archimedean with a stated turn separation, so the crossing threshold can be predicted before it is counted rather than discovered.

Every deviation reported is measured back from the original vertices to the simplified polyline, segment by segment with the projection clamped to each segment’s ends. Measuring to the infinite line through a segment instead is the classical statement of the algorithm and is not the bound it promises: the two differ exactly when a vertex projects past an endpoint, which is what a curve that runs out along its own chord and comes back does.

Where the model stops #

Douglas–Peucker and Visvalingam only. Real cartographic generalisation is much more than vertex reduction: it displaces features so they do not collide, merges them, exaggerates them so they stay visible, and selects among them. Every one of those operations breaks more guarantees than these two do, and none of them is measured here.

No topological repair. Production pipelines run a validity check after simplifying and fix what it finds, and a good one uses a topology-preserving variant that never introduces a crossing in the first place. The point of the spiral is not that crossings are unavoidable; it is that the plain algorithm’s guarantee does not exclude them, so anyone relying on the guarantee alone is relying on something it does not say.

One shape and one spiral. The flip counts scale with perimeter × ε and the crossing threshold with the separation between the parts of the curve, and both of those are statements about any curve. The specific numbers — fifty-one flips at ε = 0.032, a crossing at twice the gap — belong to these two objects. What transfers is the shape of the dependence, not the constants.

And the containment probes are uniform. Real query points are not spread evenly over a bounding box — they cluster where people are, which is often near boundaries because boundaries follow rivers and roads. The fraction of real queries affected is therefore higher than the fraction of area affected, by an amount nothing here measures.

The generalisation #

An approximation’s error bound is stated in one quantity, and every other quantity derived from the approximation has its own error, which does not follow. That is a general fact about bounds and it is why numerical analysis distinguishes forward error from backward error at all.

What makes the cartographic case instructive is how reasonable the substitution feels. A boundary moved by less than a fifth of a millimetre on the page is, in the ordinary sense, the same boundary. The area is a fifth of a millimetre different, the containment answers are a fifth of a millimetre different, and the curve is a fifth of a millimetre from being simple — but “a fifth of a millimetre from being simple” is not a thing. Some properties degrade continuously with the perturbation and some are binary, and a bound on the perturbation says nothing about the second kind.

There is a second habit underneath it, and this collection has now met it three times. A check that measures the approximation with the approximation’s own metric cannot fail for the one reason the promise could. The bound above is measured to the segment, not to the infinite line through the segment, and the difference between those two measurements is invisible on every ordinary curve and unbounded on a curve that doubles back. A validation suite written by whoever wrote the algorithm, on the same afternoon, tends to reach for the same expression — and then it agrees with itself.

The transferable habit: when an approximation is introduced, list the quantities that will be read off it afterwards, and check each one separately, with a measurement that does not share the approximation’s arithmetic. The list is usually longer than the person choosing the tolerance expects, and it usually includes at least one property that has no continuous version.

Who found it, and when #

The area and topology failures were noticed within a decade of the algorithm’s publication. The topology-preserving literature begins in earnest with Alan Saalfeld’s 1999 paper on making Douglas–Peucker preserve simplicity, which adds a check against the neighbouring geometry that the original had no reason to include — the original was written for a single line, and the failure only exists between lines or between a line and itself.

Visvalingam and Whyatt published their area-based rule in 1993 in The Cartographic Journal, arguing explicitly that the distance criterion keeps the wrong things: it preserves spikes because a spike is far from a chord, while an eye reading a coastline is following the large shapes. That argument is about what a map is for, and it is why the two algorithms coexist rather than one having replaced the other.

The containment consequence has no single citation, which is itself informative. It surfaces in land-administration practice as the rule that boundaries of legal effect are not generalised, and in statistical geography as the practice of publishing a high-resolution boundary set for analysis and a low-resolution one for display, with the two carrying different identifiers so nobody joins across them.

Where the ladder goes next #

This anchor now has its three rungs: a length that depends on the ruler, an operation that does not commute with the projection, and a tolerance that promises less than it appears to. What it has not done is put a number on the benefit — the bytes saved, the drawing time bought — against which every one of these costs is traded. That comparison needs the display side of the collection, where the tile pyramid already measures what a level of detail costs to serve.