Let and be two vectors in . In the last post we showed that and generate (as an abelian group under , or a -module) iff the parallelogram determined by them has unit area.
Define a lattice polygon to be a polygon whose vertices are lattice points, i.e. points in . Note that and generate iff the parallelogram determined by them contains no further lattice points. (In the language of groups, iff the quotient is trivial.) Hence:
Lemma 1. A lattice parallelogram has unit area iff it contains no further lattice points.
This can also be phrased in terms of lattice triangles:
Lemma 2. A lattice triangle has area iff it contains no further lattice points.
Call such triangles elementary. We can use lemma 2 to prove Pick’s theorem:
Theorem (Pick). A lattice polygon has area , where and are the number of interior and boundary lattice points respectively.
Proof. Triangulate the polygon into elementary triangles, then induct on the number of elementary triangles. (If the polygon can be triangulated into and also into elementary triangles, then its area by lemma 2 is which shows that the number is well-defined.)
Consider an elementary triangle on the boundary. There are two possibilities:
- All three vertices lie on the boundary. In this case deletion of the triangle reduces by and keeps fixed. By the induction hypothesis the new polygon has area , and so the area of the original polygon is .
- One of the vertices is an interior point. Then deletion of the triangle increases by , but reduces by . Hence by the induction hypothesis the new polygon has area , and so the area of the original polygon is .
Finally, the base case follows from lemma 2. Hence the proof is complete.
Corollary. In any triangulation of a lattice polygon into elementary triangles, the number of elementary triangles is .