LattE background
 
Home | People | Software | Theory | Background | UC Davis Math
 
Pick's theorem

Pick's theorem

Theorem 1   Given a simple closed polygon whose vertices have integer coordinates, then

$\displaystyle Area(P) = ($# interior lattice points$\displaystyle ) + \frac{1}{2}($# boundary lattice points$\displaystyle ) - 1 $

Clearly we can reduce Pick's Theorem to the case of triangles because

\includegraphics[scale=.75]{A1A2.eps}


  $\displaystyle A$ $\displaystyle =$ $\displaystyle A_1 + A_2$
  $\displaystyle I$ $\displaystyle =$ $\displaystyle I_1 + I_2 + L - 2$
  $\displaystyle B$ $\displaystyle =$ $\displaystyle B_1 + B_2 - 2L + 2$

where $ A=$area, $ I=$# interior lattice points, and $ B=$# boundary points. These all imply
  $\displaystyle I + \frac{1}{2}B - 1$ $\displaystyle =$ $\displaystyle (I_1 + I_2 + L - 2) + (\frac{1}{2}B_1 + \frac{1}{2}B_2 - L + 1) - 1$
    $\displaystyle =$ $\displaystyle (I_1 + \frac{1}{2}B_1 - 1) + (I_2 + \frac{1}{2}B_2 - 1)$

We may further assume that there are no other lattice points other than its vertices. Now the idea is to embed the special triangles into rectangles.
Figure 1: Examples of special triangles embedded in rectangles
\includegraphics[scale=.5]{all4cases.eps}
Thus, all the problem reduces to is to study and show that Pick's theorem is true for
  1. Rectangles.
  2. Right angle triangles with integer vertices and no lattice points in the hypotenuse.

For a triangle of case 1

\includegraphics[scale=.5]{case0.eps}

$\displaystyle A=\frac{1}{2}ab$, $\displaystyle B=a+b+1 $

By thinking of the triangle as a rectangle,

   # of interior points$\displaystyle = \frac{1}{2}(a-1)(b-1). $

It's crucial that there are no lattice points in the hypotenuse. QED.


Going back to the case of an arbitrary polygon, there is an alogrithm that can be used to count the number of lattice points inside of it:

  1. Triangulate polygon.
  2. Count lattice points in each triangle (there are $ (n-2)$ of them). Call this number $ x$ .
  3. Count lattice points on each diagonal. Call this number $ y$ .
  4. $ x - y =$   Result .

Definition 2   Let $ \Delta$ be a triangle whose vertices are integral. We say $ \Delta$ is primitive if it has no other lattice opints in its boundary or interior.
Figure 2: Examples of primitive triangles
\includegraphics[scale=.5]{primtris.eps}

Lemma 3   Every lattice triangle can be divided into primitive triangles.
\includegraphics[scale=.5]{divprim.eps}

Lemma 4   A primitive triangle has area $ =\frac{1}{2}$ .

Lemma 5   Euler's formula: In a triangulation of a polygon,

$\displaystyle V-E+T=1, $

where $ V=$# vertices in primitive triangulation , $ E=$# edge segments in prmitive triangulation , and $ T=$# primitive triangles .

Corollary 6   The number of primitive triangles from the first lemma is

$\displaystyle 2i(p)+b(p)-2, $

where $ i(p)=$# interior points and $ b(p)=$# boundary points .

The proof of the third lemma can be done using the corollary and the first lemma:

  $\displaystyle Area(P)$ $\displaystyle =$ $\displaystyle \sum$   (area of primitive triangles)
    $\displaystyle =$ $\displaystyle \frac{1}{2}$# primitive triangles
    $\displaystyle =$ $\displaystyle \frac{1}{2}(2i(p)+b(p)-2)$
    $\displaystyle =$ $\displaystyle i(p) + \frac{1}{2}b(p) - 1.$

The proof of the corollary can be done using the second lemma.

  1. I wish to write $ E$ in terms of $ T$
    (1) $\displaystyle \frac{1}{2}(3T+b(p)) = E$    

  2. We have $ V = i(p) + b(p)$ and $ T=1-E-V$
  3. Substituting equation (1) into the equations from number 2, we get
      $\displaystyle T$ $\displaystyle =$ $\displaystyle 1 - \frac{1}{2}(3T+b(p)) - (i(p)+b(p))$
      $\displaystyle -\frac{1}{2}T$ $\displaystyle =$ $\displaystyle 1 - i(p) - \frac{1}{2}b(p)$
      $\displaystyle T$ $\displaystyle =$ $\displaystyle 2i(p) + b(p) - 2.$

  4. DONE.

The proof of the second lemma goes as follows:

  1. Any triangle can be sandwiched into a rectangle with sides parallel to the $ x,y$ axis. The proof should be done for all cases, but we will show the hardest case and the simpler proofs can follow.
    Figure 3: The ``hardest'' primitive triangle case
    \includegraphics[scale=.5]{ecase3.eps}
  2. From the above picture we get the following equations:
    1. $ S(ACE)=\frac{qs}{2}$
    2. $ S(ABD)=\frac{pr}{2}$
    3. $ S(BCF)=\frac{(q-p)(s-r)}{2}$
    4. $ S(BDEF)=(q-p)r$
    which all imply

    $\displaystyle S(ABC)=\frac{qs}{2}-\frac{pr}{2}-\frac{(q-p)(s-r)}{2}-(q-p)r=\frac{1}{2}(ps-qr). $

  3. So, if we can show $ ps-qr=1$ , then we are done.
  4. To help us show the above we need to define a new notation
      $\displaystyle N(M)$ $\displaystyle =$ # of lattice points inside but not on the boundary of polygon M
      $\displaystyle N(PQ)$ $\displaystyle =$ # of lattice points lying on the segment PQ except its ends

  5. Now we look at two ways to represent $ N(ACE)$ :
      $\displaystyle N(ACE)$ $\displaystyle =$ $\displaystyle \frac{1}{2}(q-1)(s-1)$
      $\displaystyle N(ACE)$ $\displaystyle =$ $\displaystyle N(ABC) + N(ABD) + N(BCF)$
          $\displaystyle + N(BDEF) + N(AB) + N(BC)$
          $\displaystyle + N(BD) + N(BF) + 1,$

    where the ending $ 1$ comes from the point $ B$ .
  6. Then write the above in terms of $ p, q, r, s$ to get
      $\displaystyle \frac{1}{2}(q-1)(s-1)$ $\displaystyle =$ $\displaystyle \frac{1}{2}(p-1)(r-1) + \frac{1}{2}(q-p-1)(s-r-1)$
          $\displaystyle + (q-p-1)(r-1) + (r-1) + (q-p-1) + 1$

  7. After simplification we get,

    $\displaystyle ps-qr=1 $

  8. DONE!


De Loera account latte 2006-10-20