Pick's Theorem

A polygon without self-intersections is called a lattice if all its vertices are the points with integer coordinates

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.