Pick's Theorem for the Area of a Lattice Polygon

Let P be a polygon in the plane whose vertices have integer coordinates.  The area of P can be determined by counting the lattice points on the interior and boundary of the polygon.  Let i be the number of interior lattice points in P, and b be the number of boundary lattice points on P.  Then,

Area(P) = i + (b/2) - 1

Proof:

Lemma 1: If a polygon, P, is divided by a path whose endpoints are on lattice points of P into two smaller polygons, P1 and P2, then Pick's formula gives Area(P1)+Area(P2)=Area(P).

This can be seen as follows.  The interior lattice points of P all fall into the interior of P1 (i1 of them) or the interior of P2 (i2 of them) or on the path that was drawn to divide P (i3 of them), so i1+i2+i3=i.  Two of the boundary points of P (b3=2) are the endpoints of the dividing path that formed P1 and P2.  b1 other boundary points are boundary points of P1, and b2 boundary points are boundary points of P2, so b1+b2+b3=b.

By Pick's formula,

Area(P1) = i1+(b1+b3+i3)/2-1, and
Area(P2) = i2+(b2+b3+i3)/2-1,

so

Area(P1)+Area(P2) = i1+(b1+b3+i3)/2-1 + i2+(b2+b3+i3)/2-1
 = i1+i2+i3 + (b1+b2+2b3)/2 - 2
 = i + (b/2) + b3/2 - 2, and since b3=2, we have
 = 1 + (b/2) - 1
 = Area(P)

Lemma 2: A polygon, P, with 3 boundary points and no interior point has area 1/2.

Start by translating the polygon so one of its points is on the origin.  From the origin, we will call a lattice point (x,y) "visible" if GCD(x,y)=1.  Two lattice points (x₁,y₁), (x₂,y₂), in which the largest x- or y- coordinate (in absolute value) is n, will be called n-Farey-adjacent if, from the point of view of the origin, no other lattice point with coordinates no larger than n is visible between them.

A triangle formed by the origin and two n-Farey-adjacent lattice points is a Farey triangle, which means  x₁/y₁ and x₂/y₂ are adjacent elements of a Farey sequence, which means that |x₁y₂ - y₁x₂| = 1, hence the area of the triangle formed by (0,0), (x₁,y₁), abd (x₂,y₂) is 1/2.

Proof of Pick's Theorem: Every n-sided polygon (n>3) can be subdivided into two polygons each with fewer than n sides.  By repeating this action, a polygon can be completely decomposed into triangles.  A triangle with n interior lattice points can be decomposed into three triangles, each with fewer than n interior lattice points by drawing a line from the each vertex to one interior lattice point.  By repeating this action, every triangle can be completely decomposed into triangles with no interior lattice points.  A triangle with n>3 boundary points can be divided into two triangles, each with fewer than n boundary points by drawing a line from a non-vertex boundary point to the opposite vertex.  By repeating this action, every polygon can be completely decomposed into triangles with no interior lattice points and only three vertex points.  By Lemma 1, each subdivision of the polygon kept the same area by Pick's formula, and by Lemma 2, Pick's formula is correct for the smallest units.

Parallelogram of Area 4

Minkowski's theorem: If a parallelogram A whose middle point is the origin has the area 4, then besides the origin, there is at least one lattice point inside A or on its boundary.  This theorem generalizes to n dimensions.

Internet References:

Cut the knot: Pick's Theorem: An Interactive Activity 

Wikipedia: Minkowski's theorem 

Related pages in this website:

Summary of geometrical theorems

Farey sequences, and their application to Pick's Theorem

Triangle Area using Determinant

Triangle Area using Vectors

Polygon Area using Determinant

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]