Pick's Theorem, Area by Counting Dots, math that surprises you lesson

Draw a polygon on square grid paper with every corner on a grid point. Its sides may slope in any direction, so cutting it into rectangles and triangles to find its area can be awkward. Can counting the dots inside it and on its edges give its exact area instead? This page states Pick’s theorem, which says yes for polygons without holes, checks it on a pentagon, and explains where the half and the minus one in the formula come from.

Key terms

Pick’s theorem

Definition Pick’s theorem is a formula for the area of a polygon drawn on the square grid of points with whole-number coordinates. It has two conditions. Every vertex of the polygon must be a grid point, and the polygon must be simple, which means that its boundary is one closed path of straight edges that never crosses or touches itself, so the polygon has no holes. Under these conditions, let $I$ be the number of grid points strictly inside the polygon and $B$ the number of grid points on its boundary, vertices included. Then the area of the polygon is

A = I + \frac{B}{2} - 1

square units of the grid. The polygon does not have to be convex, and its edges may slope in any direction. The theorem was published by Georg Pick in 1899.

In plain words Each dot inside counts as a whole square unit, each dot on the boundary counts as half of one, and then one is taken away. Nothing has to be measured, only counted.

Example Start with the $4$ by $4$ square with corners $(0, 0)$ , $(4, 0)$ , $(4, 4)$ and $(0, 4)$ , and cut off the corner triangle with vertices $(4, 2)$ , $(4, 4)$ and $(2, 4)$ . What is left is the pentagon with vertices $(0, 0)$ , $(4, 0)$ , $(4, 2)$ , $(2, 4)$ and $(0, 4)$ . The triangle has legs $2$ and $2$ and area $2$ , so the pentagon has area $16 - 2 = 14$ . Now count instead. Strictly inside the pentagon lie three grid points in the row $y = 1$ , three in the row $y = 2$ and two in the row $y = 3$ , so $I = 8$ . The boundary holds the $5$ vertices, three more points on the bottom edge, three on the left edge, one on the right edge, one on the top edge and the point $(3, 3)$ on the sloping edge, so $B = 14$ . Pick’s theorem gives

8 + \frac{14}{2} - 1 = 14,

the same area as the cutting.

Lattice points

Definition A lattice point, or grid point, is a point $(x, y)$ of the plane whose coordinates $x$ and $y$ are both whole numbers. Together these points form the square lattice, in which neighboring points are one unit apart. Take a segment whose ends are lattice points that lie $a$ units apart horizontally and $b$ units apart vertically, not both zero, and let $g$ be the greatest common divisor of $a$ and $b$ , the largest whole number that divides both, which is $a$ itself when $b = 0$ . Then the segment contains exactly $g + 1$ lattice points, both ends included, and they split it into $g$ equal steps. For a simple lattice polygon each edge therefore adds $g$ points to the boundary count $B$ , its points other than the end it shares with the next edge, so $B$ is the sum of $g$ over all the edges.

In plain words The lattice is the set of dots on grid paper. A sloping edge can pass through dots between its ends, and the greatest common divisor tells you how many.

Example The sloping edge of the pentagon runs from $(4, 2)$ to $(2, 4)$ , which is $2$ units across and $2$ units up. The greatest common divisor of $2$ and $2$ is $2$ , so the edge holds $3$ lattice points, $(4, 2)$ , $(3, 3)$ and $(2, 4)$ . Going around the pentagon from $(0, 0)$ , the edges have $g = 4$ , $2$ , $2$ , $2$ and $4$ , so

B = 4 + 2 + 2 + 2 + 4 = 14.

An edge from $(0, 0)$ to $(6, 4)$ has $g = 2$ and three lattice points, $(0, 0)$ , $(3, 2)$ and $(6, 4)$ , while an edge from $(0, 0)$ to $(5, 3)$ has $g = 1$ and passes through no lattice point between its ends.

Lattice polygon

Definition A lattice polygon is a polygon whose vertices are all lattice points. Its edges may pass through further lattice points between the vertices, and those points count toward $B$ as well. Pick’s theorem holds for every simple lattice polygon. It says nothing about a polygon with a vertex off the lattice, and it needs a correction for a region with holes. Suppose the region lies inside a simple lattice polygon and has $h$ holes cut out of it, each hole the inside of a simple lattice polygon, with the holes lying strictly inside the outer polygon and not touching one another. If $B$ counts the lattice points on the outer boundary and on the boundaries of all the holes, and $I$ counts the lattice points strictly inside the region, then the area of the region is

A = I + \frac{B}{2} - 1 + h.

In plain words The formula needs its corners on the dots. A corner off the grid breaks the count, and each hole adds one to the value of the plain formula.

Example The square with corners $(0, 0)$ , $(\tfrac12, 0)$ , $(\tfrac12, \tfrac12)$ and $(0, \tfrac12)$ has area $\tfrac14$ . Its only lattice point is the corner $(0, 0)$ , so $I = 0$ and $B = 1$ , and the formula would give $0 + \tfrac12 - 1 = -\tfrac12$ , which cannot be an area. On a finer grid with points half a unit apart, the same square is a lattice polygon with $I = 0$ and $B = 4$ , and the formula gives $1$ small square of that grid, which is $\tfrac14$ of the original unit square. The count always measures area in squares of the grid used for counting. For a hole, take the $3$ by $3$ square with corners $(0, 0)$ and $(3, 3)$ and remove the unit square with corners $(1, 1)$ and $(2, 2)$ . The region has area $8$ , no lattice points strictly inside it and $12 + 4 = 16$ on its two boundaries, so the plain formula gives $0 + 8 - 1 = 7$ , and the corrected one gives $7 + 1 = 8$ .

Triangulation

Definition A triangulation of a polygon is a division of it into triangles that cover the whole polygon, do not overlap, and meet one another only along whole common edges or at common vertices. Every simple polygon with $n \ge 3$ vertices can be triangulated by $n - 3$ diagonals, segments inside the polygon that join two of its vertices, into $n - 2$ triangles whose vertices are vertices of the polygon. For a lattice polygon these are lattice triangles, and Pick’s theorem can be proved by building the polygon from them with a joining rule. Write $Q = I + B/2 - 1$ for any lattice polygon. Suppose two simple lattice polygons meet only along one unbroken stretch of their boundaries, such as one whole common edge, whose two ends are lattice points, and that $k$ lattice points of that stretch lie strictly between its ends. When the two polygons are joined, those $k$ points move inside, and the two ends, which both polygons counted, stay on the boundary once. So the joined polygon has

\begin{gathered} I = I_1 + I_2 + k, \\[0.4em] B = B_1 + B_2 - 2k - 2, \end{gathered}

and therefore $Q = Q_1 + Q_2$ . The quantity $Q$ adds up under joining exactly as area does.

In plain words Cut a polygon into triangles, check the formula on each triangle, and the bookkeeping of shared points glues the answers back together. The minus one is what makes the two shared ends come out right.

Example Triangulate the pentagon by the diagonals from $(0, 0)$ to $(4, 2)$ and to $(2, 4)$ . The three triangles have areas $4$ , $6$ and $4$ , and their counts $(I, B)$ are $(1, 8)$ , $(4, 6)$ and $(1, 8)$ , so each one satisfies Pick’s theorem. Each diagonal has one lattice point between its ends, $(2, 1)$ and $(1, 2)$ , so $k = 1$ at each joint. Joining the first two triangles gives $I = 1 + 4 + 1 = 6$ and $B = 8 + 6 - 2 - 2 = 10$ , and adding the third gives

\begin{aligned} I &= 6 + 1 + 1 = 8, \\[0.4em] B &= 10 + 8 - 2 - 2 = 14, \end{aligned}

the counts found before. The same rule proves the theorem in four steps. A $w$ by $h$ rectangle with sides along the grid lines has $(w - 1)(h - 1)$ points inside and $2w + 2h$ on its boundary, so

\begin{aligned} Q &= (w - 1)(h - 1) \\[0.4em] &\quad + (w + h) - 1 \\[0.4em] &= wh, \end{aligned}

its area. A diagonal cuts the rectangle into two right triangles, and a half turn about the center of the rectangle carries one triangle onto the other and grid points onto grid points, so the two have the same $Q$ . By the joining rule, with the diagonal as the shared edge, their values of $Q$ add up to $wh$ , so each is $wh/2$ , the area of the triangle. Any lattice triangle sits in a smallest rectangle with sides along the grid lines, and the rest of that rectangle splits into right triangles of this kind and at most one smaller rectangle, so the joining rule, used in reverse, gives the triangle a value of $Q$ equal to its area. Finally, a triangulation builds any simple lattice polygon from lattice triangles, joined one at a time in an order in which each new triangle meets the part already built along one edge.

Check yourself

Cut a bigger corner off the $4$ by $4$ square, the triangle with vertices $(4, 1)$ , $(4, 4)$ and $(1, 4)$ . For the pentagon that is left, with vertices $(0, 0)$ , $(4, 0)$ , $(4, 1)$ , $(1, 4)$ and $(0, 4)$ , count $I$ and $B$ and check Pick’s theorem against the area found by cutting.

Show the answer

The removed triangle has legs $3$ and $3$ and area $\tfrac92$ , so the pentagon has area $16 - \tfrac92 = \tfrac{23}{2}$ . The sloping edge from $(4, 1)$ to $(1, 4)$ goes $3$ across and $3$ up, so $g = 3$ and it holds the $4$ points $(4, 1)$ , $(3, 2)$ , $(2, 3)$ and $(1, 4)$ . Around the pentagon the edges have $g = 4$ , $1$ , $3$ , $1$ and $4$ , so $B = 13$ . The points strictly inside are those with whole coordinates from $1$ to $3$ and $x + y < 5$ , three in the row $y = 1$ , two in the row $y = 2$ and one in the row $y = 3$ , so $I = 6$ . Pick’s theorem gives

6 + \frac{13}{2} - 1 = \frac{23}{2},

which matches. An odd number of boundary points goes with an area that ends in a half.

Change a rule by allowing a hole. Take the $3$ by $3$ square with corners $(0, 0)$ and $(3, 3)$ and remove the unit square with corners $(1, 1)$ and $(2, 2)$ . The plain formula gives $7$ but the area is $8$ . Cut the region into two simple lattice polygons and use the joining rule to see where the missing $1$ goes.

Show the answer

Cut along the segments from $(1, 0)$ to $(1, 1)$ and from $(2, 2)$ to $(2, 3)$ . One piece is the L shape with vertices $(0, 0)$ , $(1, 0)$ , $(1, 2)$ , $(2, 2)$ , $(2, 3)$ and $(0, 3)$ , and the other is the L shape with vertices $(1, 0)$ , $(3, 0)$ , $(3, 3)$ , $(2, 3)$ , $(2, 1)$ and $(1, 1)$ . Each has area $4$ , no lattice points inside and $10$ on its boundary, so Pick’s theorem holds for each, since $0 + 5 - 1 = 4$ . The two pieces meet along two separate segments, not one unbroken stretch. Neither segment has lattice points between its ends, and each segment has two ends that both pieces counted, so

\begin{aligned} I &= 0 + 0 = 0, \\[0.4em] B &= 10 + 10 - 4 = 16. \end{aligned}

Then $Q = 0 + 8 - 1 = 7$ , while $Q_1 + Q_2 = 8$ . Joining along one stretch keeps $Q$ additive, but the second stretch, which closes a loop around the hole, removes two more ends and lowers $Q$ by one more. That is the $+h$ in the corrected formula, which gives $7 + 1 = 8$ .

Extend the pattern. A lattice triangle has no lattice points at all except its three vertices. What does Pick’s theorem say about its area? Check the answer on the long thin triangle with vertices $(0, 0)$ , $(1, 0)$ and $(5, 1)$ .

Show the answer

Such a triangle has $I = 0$ and $B = 3$ , so its area is

0 + \frac{3}{2} - 1 = \frac12,

however long or thin it is. The triangle with vertices $(0, 0)$ , $(1, 0)$ and $(5, 1)$ lies in the strip $0 \le y \le 1$ . Its only lattice points with $y = 0$ are $(0, 0)$ and $(1, 0)$ , and its only one with $y = 1$ is $(5, 1)$ , so it has no others. Its base from $(0, 0)$ to $(1, 0)$ has length $1$ and its height is $1$ , so its area is $\tfrac12 \cdot 1 \cdot 1 = \tfrac12$ , as predicted. It follows that any simple lattice polygon cut into triangles of this kind, which can always be done by using all of its lattice points as vertices, is cut into exactly $2A = 2I + B - 2$ of them. The pentagon of area $14$ needs $28$ .