Pick's theorem

For the theorem in complex analysis, see Schwarz lemma § Schwarz–Pick theorem.

i = 7, b = 8, A = i + ⁠b/2⁠ − 1 = 10

In geometry, Pick's theorem provides a formula for the area of a simple polygon with integer vertex coordinates, in terms of the number of integer points within it and on its boundary. The result was first described by Georg Alexander Pick in 1899, and popularized in English by Hugo Steinhaus in the 1950 edition of his book Mathematical Snapshots. It has multiple proofs, and can be generalized to formulas for certain kinds of non-simple polygons.

Formula

Suppose that a polygon has integer coordinates for all of its vertices, let $i$ be the number of integer points that are interior to the polygon, and let $b$ be the number of integer points on its boundary (including vertices as well as points along the sides of the polygon). Then the area $A$ of this polygon is: $$A=i+{\frac {b}{2}}-1.$$ The example shown has $i=7$ interior points and $b=8$ boundary points, so its area is $A=7+{\tfrac {8}{2}}-1=10$ square units.

Proofs

Via Euler's formula

One proof of this theorem uses Euler's polyhedral formula to reduce the problem to the case of a triangle with three integer vertices and no other integer points. Such a triangle can tile the plane by copies of itself, rotated by 180° around the midpoint of each edge. The triangles of this tiling are twice as dense as the integer points (each integer point belongs to six triangles, while each triangle touches only three integer points) from which it follows that their area is exactly ${\tfrac {1}{2}}$, as Pick's theorem (once it has been proved) would also imply. It is also possible to use Minkowski's theorem on lattice points in symmetric convex sets to prove that these triangles have area ${\tfrac {1}{2}}$.

Any other simple polygon can be subdivided into triangles of this type. If the polygon has $i$ interior integer points, $b$ boundary points, and area $A$, then we can use these numbers of points to count the vertices, faces, and edges of the subdivision, used by Euler's formula. The interior and boundary points are the vertices of the subdivision, so there are $i+b$ total vertices. The subdivision has $2A+1$ faces: $2A$ triangles of area ${\tfrac {1}{2}}$ to cover the area of the polygon, and one more face outside the polygon. Finally, each edge of the subdivision forms the side of one or two triangles. There are $6A$ sides of triangles, and $b$ edges of the subdivision that only form the side of one triangle rather than two, so the total number of edges in the subdivision is ${\tfrac {6A+b}{2}}$. Plugging these numbers into Euler's formula $V-E+F=2$ gives $$(i+b)-{\frac {6A+b}{2}}+(2A+1)=2,$$ and Pick's formula can be obtained by simplifying this linear equation and solving for $A$. Alternatively, the number of edges can be calculated as $3i+2b-3$, leading to the same result.

It is also possible to go the other direction, using Pick's theorem (proved in a different way) as the basis for a proof of Euler's formula.

Other proofs

Alternative proofs of Pick's theorem that do not use Euler's formula include the following.

• One can recursively decompose the given polygon into triangles, allowing some triangles of the subdivision to have area larger than 1/2. Both the area and the counts of points used in Pick's formula add together in the same way, so the truth of Pick's formula for general polygons follows from its truth for triangles. Any triangle subdivides its bounding box into the triangle itself and additional right triangles, and the areas of both the bounding box and the right triangles are easy to compute. Combining these area computations gives Pick's formula for triangles, and combining triangles gives Pick's formula for arbitrary polygons.
• The Voronoi diagram of the integer grid subdivides the plane into squares, centered around each grid point. One can compute the area of any polygon as the sum of its areas within each cell of this diagram. For each interior grid point of the polygon, the entire Voronoi cell is covered by the polygon. Grid points on an edge of the polygon have half of their Voronoi cell covered. The Voronoi cells of corner points are covered by amounts whose differences from half a square (using an argument based on turning number) total to the $-1$ correction term in Pick's formula.
• Alternatively, instead of using grid squares centered on the grid points, it is possible to use grid squares having their vertices at the grid points. These grid squares cut the given polygon into pieces, which can be rearranged (by matching up pairs of squares along each edge of the polygon) into a polyomino with the same area.
• Pick's theorem may also be proved based on complex integration of a doubly periodic function related to Weierstrass's elliptic functions.
• Applying the Poisson summation formula to the characteristic function of the polygon leads to another proof.

Generalizations

Generalizations to Pick's theorem to non-simple polygons are possible, but are more complicated and require more information than just the number of interior and boundary vertices. For instance, a polygon with $h$ holes bounded by simple integer polygons, disjoint from each other and from the boundary, has area $$A=i+{\frac {b}{2}}+h-1.$$ It is also possible to generalize Pick's theorem to regions bounded by more complex planar straight-line graphs with integer vertex coordinates, using additional terms defined using the Euler characteristic of the region and its boundary, or to polygons with a single boundary polygon that can cross itself, using a formula involving the winding number of the polygon around each integer point as well as its total winding number.

The Reeve tetrahedra in three dimensions have four integer points as vertices and contain no other integer points. However, they do not all have the same volume as each other. Therefore, there can be no analogue of Pick's theorem in three dimensions that expresses the volume of a polytope as a function only of its numbers of interior and boundary points. However, these volumes can instead be expressed using Ehrhart polynomials.

See also

• Blichfeldt's theorem, on translating any shape so that it contains at least its area in grid points
• Dot planimeter, a transparency-based device for estimating area by counting grid points
• Farey sequence, an ordered sequence of rational numbers with bounded denominators whose analysis involves Pick's theorem
• Gauss circle problem, the problem of bounding the error between the areas and numbers of grid points in circles
• Integer points in convex polyhedra, a counting problem arising in several areas of mathematics and computer science
• Shoelace formula, a different formula for area using only the consecutive vertices of a polygon

External links

• Pick's Theorem by Ed Pegg, Jr., the Wolfram Demonstrations Project.
• Pi using Pick's Theorem by Mark Dabbs, GeoGebra