Pick's Theorem: A Simple Lattice Polygon Has Area I + B/2 - 1

The statement, and exactly what it assumes

Fix the integer lattice ℤ², the set of plane points with both coordinates whole numbers. A lattice polygon is a simple polygon — one closed, non-self-intersecting boundary made of finitely many straight segments — whose every vertex lies in ℤ². Let I be the number of lattice points strictly inside it and B the number on its boundary. Pick's Theorem is the identity A = I + B/2 − 1.

Four hypotheses are load-bearing, and each one fails loudly if dropped:

• Every vertex is a lattice point. The triangle (0,0), (1,0), (0,½) has area ¼, which is not a whole number of halves, so no version of the formula can produce it.
• The polygon is simple. A self-crossing boundary encloses signed regions with overlapping multiplicities; ‘inside’ is no longer well defined and the identity says nothing about it.
• No holes. The region must be simply connected. With h holes the corrected statement is A = I + B/2 + h − 1.
• B counts every boundary lattice point, not just corners. The edge from (2, 4) to (2, 2) passes through (2, 3), and (2, 3) counts. In general an edge with displacement (Δx, Δy) carries gcd(|Δx|, |Δy|) + 1 lattice points including both endpoints, so B = ∑_edges gcd(|Δx|, |Δy|) counts each vertex exactly once.

Conspicuously absent from that list: convexity. Pick's Theorem holds verbatim for spiky, deeply non-convex polygons. One immediate corollary is worth naming, because it is the identity's fingerprint: rearranged, 2A = 2I + B − 2, and the right-hand side is an integer. So every lattice polygon has an area that is a whole number of halves. There is no lattice polygon of area 0.4, or π/4, or one third.

A worked example you can check by hand

Take the pentagon with vertices (1, 1), (5, 2), (4, 5), (2, 4), (2, 2), listed counter-clockwise. It is not convex: the corner at (2, 2) is reflex.

Area, by the shoelace formula. 2A = ∑(x_iy_i+1 − x_i+1y_i) = (1·2 − 5·1) + (5·5 − 4·2) + (4·4 − 2·5) + (2·2 − 2·4) + (2·1 − 1·2) = −3 + 17 + 6 − 4 + 0 = 16, so A = 8.

Boundary count. The five edge displacements are (4, 1), (−1, 3), (−2, −1), (0, −2), (−1, −1), with gcds 1, 1, 1, 2, 1. So B = 6: the five corners plus (2, 3), which sits halfway up the vertical edge and is easy to miss.

Interior count. The lattice points strictly inside are (3, 2), (4, 2), (3, 3), (4, 3), (3, 4), (4, 4) — a tidy 2 × 3 block. So I = 6.

Pick: I + B/2 − 1 = 6 + 3 − 1 = 8. It matches the shoelace value exactly.

Now drag the single corner (4, 5) across to (5, 4) and recount. The shoelace sum becomes 15, so A = 7.5. The edge gcds become 1, 2, 3, 2, 1, giving B = 9: the point (4, 5) has left the polygon altogether, (5, 3) and (5, 4) have joined the boundary, and (3, 4) and (4, 4) have been swallowed out of the interior onto the top edge. The interior is down to (3, 2), (4, 2), (3, 3), (4, 3), so I = 4. Pick: 4 + 4.5 − 1 = 7.5. It matches again — and the half-integer area is exactly what an odd B forces.

Why it is true: additivity and primitive triangles

Write P(Q) = I(Q) + B(Q)/2 − 1 for any lattice polygon Q. The proof is two lemmas and a decomposition.

Lemma 1: P is additive. Cut Q along a lattice segment into two lattice polygons Q₁ and Q₂, and suppose that segment carries c lattice points counting both endpoints. The c − 2 points in the segment's interior belonged to neither piece's interior but do belong to Q's, so I = I₁ + I₂ + (c − 2). Those same points were counted on both sub-boundaries and are gone from Q's, and the two endpoints were double-counted, so B = B₁ + B₂ − 2(c − 2) − 2. Substituting, P(Q) = I₁ + I₂ + c − 2 + (B₁ + B₂)/2 − c + 1 − 1 = P(Q₁) + P(Q₂). Area is additive across the same cut, so if the identity holds on both pieces it holds on the whole.

Lemma 2: it holds on primitive triangles. Call a lattice triangle primitive when its only lattice points are its three vertices. Then I = 0 and B = 3, so Pick predicts area 0 + 3/2 − 1 = 1/2 — and the next section proves the area really is 1/2.

Decomposition. Every lattice polygon can be cut into primitive triangles using only lattice points as vertices: triangulate however you like (ear-clipping always works on a simple polygon), then repeatedly split any triangle holding a spare lattice point — through that point into two pieces if it lies on an edge, into three if it lies inside. The process must stop, because every lattice triangle has area at least 1/2 and each split strictly decreases area. Apply Lemma 1 back up the tree of cuts: P(polygon) = ∑P(pieces) = (number of pieces) × 1/2 = area. That is Pick's Theorem.

A by-product worth keeping: since every piece has area 1/2, any primitive triangulation of a lattice polygon uses exactly 2A = 2I + B − 2 triangles, no matter how the cuts are chosen. The pentagon above always yields 16; after the corner is dragged, always 15. The animation on this page exhibits those 16 and 15 half-unit triangles explicitly — which is a demonstration on two polygons, not a proof. The induction above is what makes it general.

There is a second classical route, through Euler's formula: regard a primitive triangulation as a planar graph, count V − E + F = 2, and Pick drops out. W. W. Funkenbusch wrote that derivation up in the American Mathematical Monthly in 1974 (vol. 81, pp. 647–648).

The half-unit lemma: why a primitive triangle has area exactly 1/2

Let T have vertices O, O + u, O + v with u, v ∈ ℤ², and suppose T's only lattice points are those three. Let Π be the parallelogram spanned by u and v. Point-reflection through the centre of Π, the map x ↦ O + u + v − x, sends ℤ² to itself (because O, u and v are integral) and swaps T with the other half of Π. So any lattice point in Π either lies in T already or is carried into T by that reflection; either way it must be a corner. Hence Π contains no lattice points beyond its four corners.

A half-open parallelogram with that property tiles the plane under lattice translation and captures exactly one lattice point per tile, so the sublattice generated by u and v is all of ℤ². Equivalently, the matrix with columns u and v is unimodular: |det(u, v)| = 1. Since area(T) = |det(u, v)|/2, the triangle has area exactly 1/2. (Minkowski's convex body theorem gives the same conclusion from a different direction.)

This is the arithmetic heart of the theorem, and it explains the otherwise mysterious −1: a primitive triangle contributes 3/2 from its three boundary points and must be trimmed back to 1/2. It also explains the theorem's symmetry group. The unimodular maps SL₂(ℤ) permute ℤ² and preserve area, so they preserve I, B and A simultaneously — which is why ‘the’ lattice polygon with given counts is only ever defined up to that group.

Where it breaks: holes, other lattices, and three dimensions

Holes. Take the 4 × 4 square [0,4]² and remove the open 2 × 2 square (1,3) × (1,3). The true area is 16 − 4 = 12. Counting: B = 16 on the outer boundary plus 8 on the inner one, so B = 24; every lattice point that would have been interior now lies on the inner boundary or inside the hole, so I = 0. Pick as stated gives 0 + 12 − 1 = 11, one short. The corrected identity is A = I + B/2 + h − 1 with h the number of holes, or, more elegantly, A = I + B/2 − χ, where χ = 1 − h is the Euler characteristic of the region. The −1 in the original statement is really −χ for a disc.

Other lattices. Nothing about Pick is special to ℤ² except its covolume. For a lattice Λ whose fundamental domain has area d, the same argument gives A = d(I + B/2 − 1) — apply the linear map carrying Λ to ℤ², which scales all areas by 1/d and leaves the counts alone. On the triangular lattice generated by (1, 0) and (1/2, √3/2), d = √3/2, so areas there are √3/2 times the Pick value.

Three dimensions: no analogue exists. John Reeve settled this in 1957 with the tetrahedron T_r = conv{(0,0,0), (1,0,0), (0,1,0), (1,1,r)}. For every positive integer r its only lattice points are the four vertices — I = 0, B = 4 — yet its volume is r/6, which grows without bound. Two solids with identical counts and different volumes kill any formula in I and B alone.

The correct generalisation is Eugène Ehrhart's, from 1962: for a lattice polytope P in ℝ^d, the counting function L_P(t) = #(tP ∩ ℤ^d) is a polynomial in t of degree d whose leading coefficient is vol(P). In the plane it reads L_P(t) = At² + (B/2)t + 1, and Pick's Theorem is nothing but the case t = 1: L_P(1) = I + B, so A + B/2 + 1 = I + B. Ehrhart–Macdonald reciprocity, L_P(−t) = (−1)^dL_{int P}(t), returns the companion identity I = A − B/2 + 1 at t = 1. In three dimensions the leading coefficient is still the volume and the next one is half the lattice-normalised surface area, but the linear coefficient is pinned down by neither — for the Reeve tetrahedron every facet is primitive, so that quadratic term is 2 and the linear term must be 1 − r/6, which turns negative once r exceeds 6. Ehrhart coefficients are not point counts, and Reeve's example is what exposes it.

What Pick's theorem proves elsewhere

No equilateral triangle fits on the integer lattice. If one did, Pick would make its area a whole number of halves, hence rational. But an equilateral triangle of side s has area (√3/4)s², and s² = (Δx)² + (Δy)² is a positive integer, so the area is irrational. Contradiction. Pushed by descent, the same idea shows the square is the only regular polygon that embeds in ℤ² at all.

Scott's inequality. Paul R. Scott proved in 1976 (Bulletin of the Australian Mathematical Society 15, 395–399) that a convex lattice polygon with at least one interior point satisfies B ≤ 2I + 7, with equality only for the triangle (0,0), (3,0), (0,3) up to unimodular equivalence. That triangle has I = 1, B = 9 and, by Pick, area 1 + 4.5 − 1 = 4.5.

Reflexive polygons and string theory. A lattice polytope is reflexive when its polar dual is again a lattice polytope; in the plane that is exactly the condition of having a single interior lattice point, and Pick immediately gives A = B/2 for all of them — the boundary count alone fixes the area. Up to unimodular equivalence there are exactly 16 such polygons. The count explodes with dimension: 4,319 reflexive polytopes in three dimensions and 473,800,776 in four, enumerated by Maximilian Kreuzer and Harald Skarke in 1998 and 2000. That four-dimensional list is the standard input for constructing Calabi–Yau hypersurfaces in mirror symmetry.

Newton polygons. The geometric genus of a generic curve with Newton polygon P equals the number of interior lattice points of P — a result going back to H. F. Baker in 1893 and sharpened by Khovanskii. Pick converts that count into an area statement: genus = A − B/2 + 1.

Farey neighbours. Two reduced fractions a/b and c/d are adjacent in a Farey sequence exactly when |ad − bc| = 1 — which is exactly the statement that the triangle (0,0), (b,a), (d,c) is primitive, and therefore has area 1/2 by the half-unit lemma. The Stern–Brocot tree is a lattice-geometry fact in disguise.

And the mundane use the theorem was built for: a geoboard, or a surveyor's grid. Lay squared paper over an irregular plot, snap the corners to grid points, and two counts give the area with no instrument more precise than an eye.

Computing with it: area, boundary counts, and interior counts

Read forwards, Pick gives area from counts. Read backwards it gives counts from area — I = A − B/2 + 1 — and that direction is the one that matters computationally, because counting lattice points one at a time is hopeless while computing an area is trivial.

For an n-vertex lattice polygon: the shoelace sum gives 2A as an exact integer in O(n) additions and multiplications; B = ∑ gcd(|Δx|, |Δy|) costs n Euclidean algorithms, O(n log C) for coordinates bounded by C; then I falls out in constant time. Note that 2A − B = 2I − 2 is always even, so the final division is exact and the whole computation can stay in integers.

The cost saved is real. A lattice polygon with coordinates up to 10⁶ can enclose on the order of 10¹² lattice points; testing them one by one at a billion tests per second takes about 17 minutes, while the Pick route is a few dozen machine operations. That gap is why lattice-point counting problems in competitive programming and on Project Euler are so often Pick problems wearing a disguise.

from math import gcd

def lattice_counts(poly):
    """poly: integer (x, y) vertices of a simple polygon, in order."""
    n = len(poly)
    twice_area = 0
    boundary = 0
    for k in range(n):
        x1, y1 = poly[k]
        x2, y2 = poly[(k + 1) % n]
        twice_area += x1 * y2 - x2 * y1          # shoelace, exact in integers
        boundary   += gcd(abs(x2 - x1), abs(y2 - y1))
    twice_area = abs(twice_area)
    area     = twice_area / 2                     # always a whole number of halves
    interior = (twice_area - boundary + 2) // 2   # Pick, rearranged: I = A - B/2 + 1
    return area, interior, boundary

print(lattice_counts([(1, 1), (5, 2), (4, 5), (2, 4), (2, 2)]))
# (8.0, 6, 6)
print(lattice_counts([(1, 1), (5, 2), (5, 4), (2, 4), (2, 2)]))
# (7.5, 4, 9)

Both printed lines are the polygons from the animation: the pentagon (area 8, I = 6, B = 6) and the same pentagon with one corner dragged (area 7.5, I = 4, B = 9).

A last historical note, because it is rarely told. Georg Alexander Pick, born in Vienna in 1859, spent his career at the German University in Prague, where he chaired the committee that brought Albert Einstein there in 1911 and pointed him towards the absolute differential calculus of Ricci-Curbastro and Levi-Civita — the machinery that became general relativity. His 1899 note ‘Geometrisches zur Zahlenlehre’ was largely overlooked for half a century until Hugo Steinhaus publicised it in Mathematical Snapshots. Pick was deported to Theresienstadt in 1942 and died there on 26 July, aged 82.

Pick's count against the true area — and the two places the hypotheses bite

Region	I (interior points)	B (boundary points)	I + B/2 − 1 versus the truth
Unit square, corners (0,0) to (1,1)	0	4	0 + 2 − 1 = 1 — correct (area 1)
Primitive triangle (0,0), (1,0), (0,1)	0	3	0 + 1.5 − 1 = 0.5 — correct (area 1/2)
Non-convex pentagon (1,1), (5,2), (4,5), (2,4), (2,2)	6	6	6 + 3 − 1 = 8 — correct (shoelace also gives 8)
4×4 square with a 2×2 square hole (h = 1)	0	24	0 + 12 − 1 = 11 — wrong; true area 12, needs the +h term
Reeve tetrahedron (0,0,0), (1,0,0), (0,1,0), (1,1,r) in 3-D	0	4	0 + 2 − 1 = 1 — wrong; volume is r/6, unbounded