Let P be a lattice polygon. Assume there are I(P) lattice points in the interior of P, and B(P) lattice points on its boundary. Let A(P) denote the area of A. Then
For every lattice point p in the interior or boundary of P, let ap denote the angle of visibility of P from p. For points in the interior of P, ap = 2. For points on the boundary other than vertices, ap = . For a vertex p, ap is just the internal angle of the polygon at that vertex. Let wp = ap/2, and introduce W(P) = wp, where the sum is taken over all lattice points either inside or on the boundary of P. Then
The proof of (1) proceeds in three steps. First, note that function W is additive. Combining two polygons that share a piece of boundary into one either replaces two boundary points with one interior point or, when the point remains a vertex, adds up the two internal angles at that vertex, one from each polygon.
Second, verify (1) for simple shapes: lattice rectangle (Case 1) with sides parallel to the grid lines, half lattice rectangle (Case 2), and arbitrary lattice triangle where we have to consider a couple of cases (Cases 3a-b.) Embed the triangle into the smallest possible rectangle from Case 1. Such a rectangle will naturally appear as a union of the given triangle and pieces from the two previous cases. Apply additivity.
Third, show that every simple lattice polygon may be dissected into a union of lattice triangles (e.g., by its diagonals.)
Equipped with (1), we now have only to compute W(P). Let P has n vertices and define b = B(P) - n. The sum of internal angles of P is (n - 2)*. At all other boundary points p (whose number is b), ap = . Therefore, wp, where the sum is taken only over boundary points is (n - 2)/2 + b/2 = (n + b)/2 - 1 = B(P)/2 - 1. Adding the sum wp over the internal points, which is simply I(P), completes the expression for W(A):
This combined with (1) proves the theorem.
Copyright © 1997 Alexander Bogomolny