Pick’s Theorem.

November 22, 2012

Motivation.

In order to teach kids about the concept of area, math teachers sometimes showed pictures which looked like

 

dots1

and we would be asked to "guess the area."  If this was being taught to younger students, the way to do it would be to draw little boxes inside and then try to see how many "half-boxes" were left, how many "quarter-boxes" were left, and so forth.  If this was a more sophisticated lesson, our teacher would instruct us to cut up the picture into rectangles and triangles — the one above, for example, has a right triangle on the left-hand side and a 4×2 rectangle on the right-hand side.  From this, we could easily use the formula for area for each, and we could deduce the total area from these. 

So far nothing is too difficult to solve.  But, if we adjust the picture slightly (still using only straight lines to construct our figure) we may get something like

 

dots3

 

Here, it is difficult to tell what to do.  We could try to find "easier" triangles to break this into, but none are immediately obvious.  It’s not easy to tell what the angles are (except by using some algebraic methods, finding slopes, etc.).  The best one could do would be to "guess" what the lengths of the sides were (or the lengths of the base and height of the triangle). 

 

Motivating Pick’s Theorem.

Before we begin, let me define some of the things we’ll be working with.   A polygon is a familiar concept, but we ought to say some things about it:

A lattice polygon is a figure on the two-dimension lattice (as above) such that all of its edges begin and end on a lattice point, no edges overlap except at a lattice point, and its boundary is a closed path (informally, this means that if we started at a lattice point and "traveled" along an edge and kept going in the same direction, we’d eventually come back to where we started).  Moreover, the polygon has to have a distinct interior and exterior (as in, it cannot look like a donut with a hole in the middle).  [Topologists, note: this means that the boundary of our figure is homeomorphic to a circle and the interior is simply connected.]

 

Easy Polygons.

The "easiest" polygons to work with in terms of area are rectangles: once we find the side lengths, we’re done.  Let’s look at the rectangle below, ignoring the stuff in the lower-left for now.

 

dots5

 

We can easily find the area here: it is a 7×3 rectangle, giving us an area of 21.  Notice something kind of neat, though; if we look at each interior point of the rectangle, we can associate a unit square with it (In the picture above, I’ve identified the point "a" with the first unit square "a", and the lattice point "b" with the square "b").  Using just the interior points, we can fill up most of this rectangle with unit squares, as below:

 

dots6

 

We see that we get "almost" all of the area accounted for if we only identify interior points like this; we miss the "¬" shape on the top.  But besides this weird shape, we learned that if we have a rectangle with n interior points, we will be able to fill up n units squared of area in our rectangle. 

If we do the same process (which I mark with a different color) for the boundary points on the top of the rectangle by identifying them with a unit square to their lower-left, we notice that we have to "skip" one on the far-left.

 

dots7

 

[For clarification, the second lattice point on the top of the rectangle corresponds to the first box, the third point corresponds with the second box, and so forth.  We are forced to skip one lattice point (the first one) on the top.]

Notice that if we have \ell interior points and k points on the top boundary of the rectangle, then there must be k-2 points in each row of interior points; hence, there must be \dfrac{\ell}{k-2} points in each column of interior points. 

Notice, last, that in our picture we need only fill in the remaining few parts on the right side.  We notice that the number of squares needed to fill in this side is exactly the same number of points in each column of interior points  (check this out on a few different rectangles if you don’t believe it). 

 

Whew.  Okay.  So.  We have \ell interior points, each corresponding to a unit square.  All but one of the top boundary points corresponds to a square; this is k - 1 unit squares.  Last, we have the number of points in each columns of the interior points corresponding to the remaining unit squares; this is \dfrac{\ell}{k-2} unit squares. 

At this point we want to write this nicely, so we’ll denote the TOTAL number of boundary points b, and note that b = 2k + 2\dfrac{\ell}{k-2}.

The total area we found was \ell + k-1 + \dfrac{\ell}{k-2}.  If we rearrange this a bit, we notice that 

\mbox{AREA} = \ell + \left(k + \dfrac{\ell}{k-2}\right) - 1 = \ell + \frac{1}{2}b - 1.

This is exactly the statement of Pick’s theorem, and it is true more generally, as we’ll see.

 

Triangles.

We’ll briefly cover one more example.  Triangles are a natural figure to think about, so let’s see if Pick’s formula works here.  First, right triangles are easy to work with, so let’s look at this one (ignore the blue part for now):

 

dots7a

 

Notice that this triangle is exactly half of a rectangle (this is completed by the blue part), and it just so happens to have no lattice points on the diagonal.  This last part is important so look again: none of the dots touch the diagonal of the red triangle (here, we are excluding the vertices of the triangle, which we don’t count as being on the diagonal).  Some come close, but none lie on it.  Of course, this is not true in general, but for now let’s just look at this triangle. 

If we use the formula above for the rectangle, we get that the area is \ell + \dfrac{b}{2} - 1 for the rectangle (in this specific case, \ell = 30 and b = 26), and half of this will be \dfrac{\ell}{2} + \dfrac{b}{4} - \dfrac{1}{2}

On the other hand, if we look at the interior points of the triangle, if none of them lie on the diagonal (like above) then we have exactly half of what the rectangle had, so our triangle has \dfrac{\ell}{2} interior points; the number of boundary points will be half of the number of boundary points of the rectangle, plus 1.  This can be seen as follows: if we consider all the points on the bottom boundary and all the points on the left boundary except for the top-most point, then this is exactly half of the boundary points of the rectangle.  Hence, the number of boundary points we have for our triangle is \dfrac{b}{2} + 1

Plugging this information into Pick’s formula (which, at this point, we only know is valid for the rectangle!) we obtain: \frac{\ell}{2} + \dfrac{b}{4} - \frac{1}{2}.  This is exactly the area we calculated before, giving us a verification that Pick’s formula works for right triangles with no lattice points on the diagonal. 

 

How do we get around the condition that no lattice points should be on the diagonal?  There is a relatively easy way to break up right triangles into other right triangles, none of which will have points on their diagonals.  I’ll demonstrate with this picture below:

dots8a

The idea is to just take the big triangle, draw some vertical and horizontal lines from the lattice points which lie on the diagonal, until you get smaller triangles (which will have no lattice points on the diagonal) and a bunch of rectangles.  In this case, I first got two triangles (a small one on top, and a small one on the bottom right) and one little 4×3 rectangle in the lower-left.  You then split the rectangle in half, which gives you some more triangles; if these triangles had lattice points on the diagonal, I would have repeated the process, getting even smaller triangles and rectangles.  Because everything is nice and finite here, we don’t get infinite numbers of rectangles and triangles and such: this process will eventually stop.  We apply the above to each and note that this verifies Pick’s formula for any right triangle.

 

But even right triangles are a bit restrictive.  It would be nice if it were true for any triangle.  Indeed, there is a similar process which decomposes triangles into right triangles.  In fact, there are a number of such processes: for example, prove to yourself that every triangle has at least one altitude which is entirely contained in the triangle, and note that this splits the triangle into two right triangles.  However you show it, this verifies Pick’s formula for any triangle.

 

 

The Theorem.

Theorem (Pick).  Given a lattice polygon with \ell interior points and b boundary points, the total area enclosed by the figure is given by \ell + \dfrac{b}{2} - 1

 

The proof of this is done by induction.  This is a more unusual type of induction since it requires us to induct on the number of triangles a figure is made up of.  The difficult part has already been completed: we have shown that the formula holds for any triangle.  We need a fact which I will not prove here:

 

Fact: Every polygon can be decomposed into a collection of triangles which only intersect at their boundaries.  Moreover, lattice polygons can be decomposed into a collection of lattice triangles (triangles whose vertices are lattice points) which only intersect at their boundaries.

 

This process is called polygon triangulation.  In layman’s terms, it means that you can take a polygon and cut it up into a bunch of triangles.  Try it yourself for a few polygons!

 

Given all of this, let’s jump into the proof.

 

Proof.  By induction.  We have already proved the formula holds for triangles, so suppose the formula holds for all polygons which are able to be decomposed into k or fewer triangles. Take such a polygon P which is able to be decomposed into exactly k triangles and "attach" a triangle T to the boundary of P such that the resulting figure is still a lattice polygon; call this new polygon Q.

 

dots9

 

 

For the triangle, denote its boundary points by b_{T} and its interior points by \ell_{T}; similarly, for P denote its boundary points by b_{P} and its interior points by \ell_{P}.  Denote the common points that T and P share by c.

For interior points, note that we have added the interior points of T and P together, but we also obtain those points which they share on their boundary, except for the two points on the vertex of the triangle which are shared; that is,  \ell_{Q} = \ell_{T} + \ell_{P} + (c-2)

 

For boundary points, we have to subtract c-2 points from P‘s boundary and  c - 2 points from T‘s boundary (for the same reason as in the previous paragraph).  If we add together the boundary points of T minus the common points and the boundary points of P minus the common points, we will be counting those two points on the vertex of the triangle which are shared two times (why?), so we need to subtract 2 so that we only count these points once.  Hence, b_{Q} = b_{P} + b_{T} - 2(c - 2) - 2 = b_{P} + b_{T} - 2c + 2

 

At this point, let A_{P} be the area of P and A_{T} be the area of T; we have that:

 

\displaystyle A_{P} + A_{T} = \left(\ell_{P} + \frac{b_{P}}{2} - 1\right) + \left(\ell_{T} + \frac{b_{T}}{2} - 1\right)

\displaystyle = (\ell_{P} + \ell_{T}) + \frac{b_{P} + b_{T}}{2} - 2

 

We note now that \ell_{P} + \ell_{T} = \ell_{Q} - (c - 2) and b_{P} + b_{T} = b_{Q} + 2c - 2 from above, which gives us

\displaystyle = \ell_{Q} - (c - 2) + \frac{b_{Q}}{2} + (c - 1) - 2 = \ell_{Q} + \frac{b_{Q}}{2} - 1.

This verifies Pick’s formula for our lattice polygon Q, and since any lattice polygon can be constructed this way (from finitely many triangles) this shows that Pick’s formula holds for any lattice polygon.  \Box