Pick's Theorem

A polygon without self-intersections is called lattice if all its vertices have integer coordinates in some 2D grid. Pick's theorem provides a way to compute the area of this polygon through the number of vertices that are lying on the boundary and the number of vertices that lie strictly inside the polygon.

Formula

Given a certain lattice polygon with non-zero area.

We denote its area by $S$, the number of points with integer coordinates lying strictly inside the polygon by $I$ and the number of points lying on polygon sides by $B$.

Then, the Pick's formula states:

$$S=I+\frac{B}{2}-1$$

In particular, if the values of $I$ and $B$ for a polygon are given, the area can be calculated in $O(1)$ without even knowing the vertices.

This formula was discovered and proven by Austrian mathematician Georg Alexander Pick in 1899.

Proof

The proof is carried out in many stages: from simple polygons to arbitrary ones:

Generalization to higher dimensions

Unfortunately, this simple and beautiful formula cannot be generalized to higher dimensions.

John Reeve demonstrated this by proposing a tetrahedron (Reeve tetrahedron) with following vertices in 1957:

$$A=(0,0,0), B=(1,0,0), C=(0,1,0), D=(1,1,k),$$

where $k$ can be any natural number. Then for any $k$, the tetrahedron $ABCD$ does not contain integer point inside it and has only $4$ points on its borders, $A, B, C, D$. Thus, the volume and surface area may vary in spite of unchanged number of points within and on boundary. Therefore, Pick's theorem doesn't allow generalizations.

However, higher dimensions still has a generalization using Ehrhart polynomials but they are quite complex and depends not only on points inside but also on the boundary of polytype.

Extra Resources

A few simple examples and a simple proof of Pick's theorem can be found here.