Area by counting dots

Area is a continuous quantity. It is what integration is for, it takes a limit to define properly, and its values are real numbers with no obligation to be anything nicer.

Put the corners of a polygon on a grid of whole-number points, though, and its area is settled exactly by two counts of dots.

Interior points, plus half the boundary points, minus one. Nothing is measured, nothing is approximated, and the two sides of the comparison are computed by methods with nothing in common: one walks round the corners multiplying coordinates, the other tests grid points for being inside.

The two counts, made honestly #

The boundary count is the easier of the two and it has a subtlety. A grid point lies on an edge from one corner to another exactly when it divides that edge in a whole-number ratio, and the number of grid points on an edge — counting one endpoint and not the other — is the greatest common divisor of the horizontal and vertical distances it spans. An edge from (0,0) to (4,6) has two, because the gcd of 4 and 6 is two; an edge from (0,0) to (3,5) has one, being only its own start.

The interior count is done by testing. Every grid point in the bounding box is put through a crossing test — the same ray rule that decides inside from outside for any polygon — and points on the boundary are excluded first, so that no dot is counted twice.

Both counts are integers, both are obtained by looking, and neither knows anything about area.

Where the half and the minus one come from #

The two odd features of the formula have one explanation between them, and the cleanest way to see it is to ask what each grid point contributes.

Think of each point as being surrounded by the polygon by some fraction of a full turn. A point strictly inside is surrounded by all of it, so it contributes one. A point on an edge but not at a corner is surrounded by half, so it contributes a half. A point at a corner contributes the fraction of a turn the polygon’s interior angle occupies.

Add all those fractions. The interior points give I. The edge points give B minus the corners, halved. And the corners give the sum of the interior angles divided by a full turn, which for a polygon with c corners is (c − 2)/2 — half the corners, less one.

Total: I + B/2 − 1. The half is the half-turn at an edge point; the minus one is the two right angles that a closed polygon’s angles always fall short of, which is the same 360-degree deficit that Euler’s formula is really about.

What the identity is really saying #

There is a way of hearing the formula that makes it less surprising and a way that makes it more so, and both are worth having.

The unsurprising reading: each interior point owns a unit square, each boundary point owns half of one, and the polygon is roughly the union of the squares owned by its points. That gives the right leading behaviour and it explains the half. It does not explain the minus one, and it is not a proof of anything, because the squares do not actually tile the polygon — they stick out in places and fall short in others.

The surprising reading: the left-hand side is a real number and the right-hand side is built from two integers with only a factor of a half between them. So the area of a lattice polygon can never be an arbitrary real number. It is always a whole number or a whole number and a half, and nothing else is reachable. A lattice polygon of area a third does not exist.

That is a genuine constraint and it is easy to check independently: twice the shoelace sum of integer coordinates is an integer, so the area is a multiple of a half. The identity says which multiple, and it says it in terms of two counts that carry no coordinates at all.

Every triangle, checked #

An identity holding on three drawn polygons is three pieces of evidence. So the figure takes every triple of points in a five-by-five grid — twenty-three hundred of them — and checks all of them.

The flat triples matter as much as the rest. A hundred and fifty-two of the triples are collinear, they have no area, and they are excluded rather than ignored: the figure asserts that the tested and the excluded add to exactly the number of triples there are, which is what makes the sweep exhaustive rather than merely large.

Six of them are drawn as a sample, and the caption says that is what they are.

Why it is true, in one move #

The exhaustive check is evidence and not a proof, and the proof is short enough to state.

The formula is additive. Cut a lattice polygon into two lattice polygons along a line between two of its grid points. Points that were interior stay interior unless they are on the cut, where they become boundary points of both halves; the cut’s endpoints are corners of both. Adding the two halves’ formulas and comparing with the whole gives an exact match, with the doubled points and the extra minus ones cancelling.

So it suffices to prove the formula for triangles that cannot be cut — those with no grid point inside and none on an edge except the three corners. For those, I = 0 and B = 3, so the formula claims an area of a half. And every such triangle does have area a half, which is a small separate argument: two copies of it fit together into a parallelogram whose corners generate the whole grid, and such a parallelogram has area one.

Every lattice polygon can be cut into such triangles, additivity carries the formula up from them, and the theorem is done. The structure — prove it for the smallest pieces, show it survives gluing — is the same structure that makes dissection proofs work, with counting in place of congruence.

What it costs, against measuring #

Both sides of the identity are computable and their costs are different in a way that decides which is used.

The shoelace formula touches each corner once. A polygon with a dozen corners costs a dozen multiplications, whatever its size, and the answer is exact in integer arithmetic — no rounding anywhere, since twice the area is a sum of products of integers.

The dot count touches every grid point in the bounding box. A polygon spanning a hundred units in each direction costs ten thousand inside-tests, and the cost grows with the size of the polygon rather than with its complexity. Scaling a shape up by ten multiplies the corner count by nothing and the dot count by a hundred.

So as a way of computing area, the identity is the wrong way round: nobody counts dots to find an area when the corners are available. Its use runs the other direction. Given a shape, the identity delivers the dot counts from the area — how many lattice points a region contains, which is the quantity number theory actually wants and which the shoelace formula says nothing about.

That reversal is common enough to be worth naming. An identity between two computable quantities is a tool for whichever of them is harder to get at, and which one that is depends entirely on what is already known.

Two awkward shapes #

Neither shape is a special case and both are worth drawing, because the formula’s two terms trade off in opposite directions. A fat shape is nearly all interior points and its area is nearly I. A shape that is mostly boundary — the comb has twenty-six boundary points against seven interior — takes most of its area from the B/2 term.

There is no convexity condition anywhere and no shape requirement of any kind, beyond having corners on the grid and not crossing itself. That is unusual for a result about polygons, and it is worth appreciating how much it rules out. Almost every classical fact about polygons needs convexity somewhere, or needs the corners in general position, or degrades into a case analysis when a reflex angle appears. Here a reflex corner contributes its own fraction of a turn like any other, the derivation never asks whether it is more or less than a half-turn, and the comb with its four concavities is handled by exactly the same three lines as the triangle.

The self-intersection condition is not decorative, though. A polygon that crosses itself has no well-defined inside — that is the whole subject of the crossing rule’s failure case — and with no inside there is no interior count and nothing for the identity to be about.

Where it does fail #

Cut a hole in the middle and the formula breaks, by exactly one.

The reason is the derivation. The angle sum of a polygon’s corners is a full turn less two right angles for a region with one boundary curve; a region with two boundaries has an extra full turn’s worth of corners, and the minus one becomes a nothing. In general a region with h holes obeys A = I + B/2 − 1 + h.

That correction term is the Euler characteristic in another costume. A disc has characteristic 1 and an annulus has characteristic 0, and the formula’s constant is exactly minus that number. So Pick’s identity is not really about polygons; it is about a region, and the constant records what kind of region it is — the same role the constant plays in every corner pays for itself, where a sphere gives 2 and a torus gives nothing.

The smallest triangles, and why they are all the same size #

The proof turns on a claim that deserves its own paragraph, because it is the only place any geometry enters: a lattice triangle with no lattice points inside it and none on its edges except its corners has area exactly one half.

It is not obvious. Such a triangle can be extremely long and thin — the corners (0,0), (1,0) and (k,1) form one for every k, and it looks nothing like a half-square. Its area is a half all the same, which the shoelace formula confirms in one line.

The reason is that the two edges leaving one corner form a basis for the whole lattice: any lattice point at all can be reached by taking whole-number multiples of them. If they did not, some lattice point would land inside the parallelogram those edges span, and that point would be inside the triangle or its mirror image. A basis of the integer lattice spans a parallelogram of area one, and the triangle is half of it.

That is the same fact behind the descent argument reaching a smallest case, and behind the observation that a change of lattice basis has determinant ±1 — which is the determinant doing the work it always does, measuring how much a map stretches area.

Where there is no version at all #

The natural next question is what happens in three dimensions: a polyhedron with corners on the integer lattice, some count of interior points, some count of points on the faces, and a formula for the volume.

There is none, and the reason is a single family of examples. Take the tetrahedron with corners at (0,0,0), (1,0,0), (0,1,0) and (1,1,r) for a whole number r. It has four lattice points on it — its own corners — and none inside, whatever r is. Its volume is r/6.

So there are tetrahedra with identical counts and unboundedly different volumes. No formula in the counts can exist, because the counts do not determine the answer. The two-dimensional result is not the first case of a pattern; it is an accident of two dimensions, and the accident is that a lattice triangle with no extra points has a fixed area while a lattice tetrahedron with no extra points does not have a fixed volume.

Something can be salvaged by counting lattice points in dilated copies of the shape, which produces a polynomial whose coefficients carry volume, surface area and more. That is a genuine generalisation and it is not a formula in two counts.

What the picture cannot show #

Every polygon here has integer corners, and that is the whole hypothesis. Move one corner by a tenth and the identity fails immediately with nothing to salvage. The figures cannot show a near-miss, because a polygon with a non-lattice corner has no boundary-point count worth taking.

The sweep is over a five-by-five grid. That is 2,148 triangles, which is a lot of evidence and no proof, and the identity is a claim about polygons of every size and shape. What makes the theorem safe is the additivity argument, which is three paragraphs of prose that no figure on this page draws.

And the counts are of dots, which are not the same as the shape. Two very different polygons can have the same I and B and therefore the same area, which is as it should be — area is not much information — but it means nothing in these figures identifies a shape, only measures one.

Where the ladder goes next #

Counting lattice points inside a region is a subject in its own right and this family’s other question is the entry to it: how many lattice points lie on a circle of a given radius, which turns out to be decided by which primes are sums of two squares.

Between the two lies the interesting general problem. The number of lattice points inside a circle of radius r is about πr², since each point owns a unit square — but how far off that estimate can be is an open question over a century old, with the answer known to lie somewhere in a range nobody has closed. Pick’s identity is the case where the error is exactly nothing, and it is exactly nothing because the boundary is made of straight lines with lattice endpoints. Curve the boundary and the error becomes the whole problem.