3. AREA OF LATTICE POLYGONS

It is clear that lattice polygons come in various shapes and sizes. A very small lattice triangle may cover just 3 lattice points – at the vertices. A very large lattice polygon might be expected to cover many more lattice points. This suggests that there might be a correlation between the area of (simple) lattice polygons and the number of lattice points they cover. Let’s see if we can find a formula. We let A stand for the area, B for the number of boundary points, and I for the number of interior points.

	A	B	I	B/2 + I – 1
(a)
(b)
(c)
(d)
(e)
(f)
(g)

You should be able to see a pattern by now. If not, add some further polygons of your own. We can now make a conjecture (educated guess) that the following theorem is true. What is it?

For the statement of the theorem and proof ...

              

3. AREA OF LATTICE POLYGONS

Our experimentation leads us to conjecture the result known as:

Pick’s Theorem: Suppose a simple lattice polygon P has area A, B boundary points and I interior points, then

                                           A = ^B/₂ + I – 1.

Note that at the moment, this result is just a guess. We may be able to find a polygon for which the result fails. We need to be able to provide a proof. The theorem appears to have been first proved in 1900 when a certain Georg Alexander Pick [P] published the result. Pick (1859–1943) was an Austrian mathematician who died in the Theresienstadt concentration camp.


Proof of Pick’s Theorem: The proof is not hard, and falls into two parts. It will be useful to associate with the polygon P the expression (function)

f(P) = A – ^B/₂ – I + 1.

We call this Pick’s formula. Then f(P) = 0 becomes the statement of Pick’s Theorem.

(1) We first show that Pick’s formula is additive. This means that if we adjoin two lattice polygons for which Pick’s formula is true to obtain a new lattice polygon P, then the formula for the new polygon P will be given by the sum of the formulae for the two contributing polygons. This will become clearer shortly.

(2) Since every lattice polygon P can be constructed by assembling together lattice triangles, Pick’s formula for P will be the sum of Pick’s formulae for all the contributing triangles. If we can show that for any such triangle T,  f(T) = 0, Pick’s Theorem will follow.

(1) Let us begin at the beginning! Look at this example:

Here we are combining two lattice polygons P₁ and P₂ to obtain a new lattice polygon P (or P₁ + P₂).
We see that in this example, Pick’s formula (and in fact, Pick’s Theorem) continue to hold for the new polygon.

	A	B	I	A – B/2 – I + 1
P1	7	8	4	0
P2	5	8	2	0
P = P1 + P2	12	12	7	0

Notice from the figure that we have added the areas, lost 1 boundary point (twice) and gained one interior point. The B column in the table appears inconsistent with this because we have also counted the two endpoints of the common segment twice.

Let’s try to work this through in general. Let P₁ have attributes A₁, B₁ and I₁ (in the obvious notation) and P₂ have A₂, B₂ and I₂. Suppose the boundary which is in common contains k lattice points. We now obtain:

	A	B	I	A – B/2 – I + 1
P1	A1	B1	I1	A1 –  B1/2 – I1 + 1
P2	A2	B2	I2	A2 –   B2/2 – I2 + 1
P = P1 + P2	A	B1 + B2 – 2k + 2	I1 + I2 + k – 2	??

Now, let’s check the final entry in the table. Using the values of A, B and I for P, we obtain:

f(P) = A – (B₁ + B₂ – 2k + 2)/₂ – (I₁ + I₂ + k – 2) + 1                               

= (A₁ + A₂) + (B₁ + B₂)/₂ – (I₁ + I₂) + 2     (the k s cancelling)     

= (A₁ –  B₁/₂ – I₁ + 1) + (A₂ –  B₂/₂ – I₂ + 1)                               

= f(P₁)  +   f(P₂).                                                                             

We say that the formula  f  is  additive  for polygons related in this way. Obviously if we wrote P₁ = P – P₂, the formula also remains true under subtraction.

(2) We now assert that any lattice polygon can be subdivided into lattice triangles, and in fact lattice triangles with boundary lattice points only at the vertices, i.e. with B = 3. Try some examples: you will be easily convinced. So by Part 1, we only need to show that Pick’s Theorem is valid for these triangles.

We observe that any lattice triangle can be placed inside a lattice rectangle with sides parallel to the coordinate axes.

There are a number of different cases to consider here, but they all involve lattice rectangles (such as R) and right-angled lattice triangles (such as P) with sides parallel to the coordinate axes. We check Pick’s Theorem for these rectangles and triangles.

Rectangle Case: Suppose the rectangle U (for example) has length l and width w.

Then in this case, A = lw,  B = 2l + 2w, and  I = (l – 1)(w – 1).
Hence
               f(U)  =  A –  ^B/₂ – I + 1  =  lw – (l + w) – (lw – l – w + 1) + 1 = 0

and Pick’s Theorem is satisfied for U.

Triangle Case: Consider now the triangle P (for example) with side lengths l and w, and by assumption, no points on the hypotenuse.

In this case, A  =  ¹/₂.lw,  B  =  l + w + 1,  I  =  ¹/₂.(l – 1)(w – 1).
Hence
            f(T)  =  A –  ^B/₂ – I + 1  =  ¹/₂.lw – ¹/₂.(l + w + 1) – 1/2.(lw – l – w + 1) + 1  =  0

and T satisfies Pick’s Theorem

Conclusion: We illustrate the final argument using the most difficult third case above.

By Part (1) of our proof

                                           f(U)  =  f(P) + f(Q) + f(R) + f(S) + f(T)
so
                                           f(T)  =  f(U) – f(P) – f(Q) – f(R) – f(S)

                                                   =  0,

since P, Q, R, S, U are all rectangles or triangles of the type covered in Part 2 of the proof.

This completes the proof of Pick’s Theorem.

A shorter but more sophisticated proof of the second part of our proof is given in Coxeter [C]. Some proofs involve showing that the area of the primitive triangle defined earlier (a lattice triangle with B = 3 and I = 0) is ¹/₂. (See Chapter 2.)

For other proofs of Pick’s Theorem you might look at Gaskell, Klamkin and Watson [GKW], Haigh [H], Varberg [V], and on the web, LattE Background [L], and Wikipedia [W].

Further results

(1) An obvious question to ask is whether an analogue of Pick’s Theorem holds in 3-space.

Experiment with a few very simple lattice polyhedra (for example, tetrahedra).
For a further hint, you might consider such tetrahedra lying within the infinite box with cross-section the unit square with vertices (0, 0), (1, 0), (1, 1), (0, 1).

After trying for yourself(!), check your result.

In 1957, Reeve [R] obtained a result in 3-space with the ingenious idea of introducing a secondary lattice – in fact the lattice of all integer multiples of (¹/₂, ¹/₂, ¹/₂). MacDonald [M] later extended this to higher dimensions. It is a nice idea, but the results lack the appealing simplicity of Pick’s Theorem.

(2) Another idea would be to ask if Pick’s Theorem remains true for non-simple lattice polygons.

There is an analogue in this case. It can be shown that

                                                               A  =  ^B/₂ + I + k,

where k is a number involving the Euler characteristic of the region and the boundary. If you are interested in following this up, see Scott [S]. However, we shall be looking at this further in Chapter 6, where we investigate the link between Pick’s Theorem and Euler’s Formula.

(3) A third question to ask is whether Pick’s Theorem continues to hold for a more general planar lattice.

The answer to this is ‘Yes’, although there needs to be a small modification in the statement of the theorem. We can obtain other lattices by transforming the integer lattice in a linear way, for example by scaling, or using a shear. Such transformations generally change the left hand side of the expression

                                                              A  =  ^B/₂ + I – 1,

but (assuming the polygon is mapped by the transformation) have no effect on the right hand side. Pick’s Theorem is valid in this more general case in the form

                                                        A/d(L)  =  ^B/₂ + I – 1,

where the term d(L) (the determinant of the lattice L defined earlier) measures the amount of area scaling carried out in obtaining L from the integer lattice.

(4) Extending this idea further, we might ask whether Pick’s Theorem has any application to non-lattice situations. Ren, Kolodziejczyk, Murphy and Reay [RKMR] apply the theorem to polygons having their vertices at the vertices of a regular hexagonal tiling to obtain area approximations. Another result of this type is obtained by Ding, Kolodziejczyk and Reay [DKR]. In these ‘hexagonal lattices’ the hexagons have no centres, and rather unsatisfactory constraints are placed on the edges of the polygons.