Home | People | Software | Theory | Background | UC Davis Math

Lattice Points of an Arbitrary Polygon

Lecture 3

In lecture 1 we looked at the number of lattice points given by circles and a certain hyperbola. Moreover, in lecture 2 we studied the number of lattice points that lie on a given line of the form $y = a x + b$. However, what is the number of lattice points that lie inside and on the boundary of an arbitrary polygon P? To study this question further let us define a polygon.

Definition: Polygon

Given n points $V_{o}$ , $V_{1}$ , $\dots$ , $V_{n-1}$ in the plane, consider the segments $E_{o}$ = $V_{o}$ $V_{1}$ , $E_{1}$ = $V_{1}$ $V_{2}$ , $\dots$ , $E_{i}$ = $V_{i}$ $V_{i+1}$ , $\dots$ , $E_{n-1}$ = $V_{n-1}$ $V_{o}$. We say that $E{o}$ , $E_{1}$ , $\dots$ , $E_{n-1}$ bound a polygon if $\dots$

1. $E_{i}$ $\cap$ $E_{i+1}$ = $V_{i+1}$
2. $E_{i}$ $\cap$ $E_{j}$ = $\phi$ $j$ $\ne$ $i$ - 1 , $j$ $\ne$ $i$ + 1 , $j$ $\ne$ $i$

In other words, a polygon is a region in the Euclidean plane bounded by line segments without self intersections.

Figure 1: A polygon with 5 vertices and 5 edges

However an arbitrary polygon need not be so simple, for instance consider the following polygon:

Figure 2: A more general Polygon

How might one go about counting the number of lattice points of a polygon such as the one in figure 2? Well, we can count by hand, which would work for this specific polygon, but suppose we had an even more general polygon than the one in figure two? One way to go about this is to see if we can break the polygon into a less complicated one. Perhaps we can take an arbitrary polygon and partition it into triangles as figure 3 suggests.

Figure 3: Triangulation of figure 2

If we can prove that every simple polygon (a polygon without holes) can be partitioned into triangles, then given a polygon P, the number of lattice points of such a polygon would be the number of lattice points given by each triangle minus the number of lattice points on each diagonal. Indeed, every simple polygon can be triangulated, but to prove this we first need to be versed with more definitions concerning polygons.

Definition: Triangulation

A partitioning of a polygon into triangles s.t. any pair of such triangles intersects on:

1. A common edge
2. A common vertex
3. Empty set

Definition

A vertex on a polygon defines two angles a non-internal angle and an internal angle the angle that intersects the interior of P is called the internal angle.

Figure 4: Call $V_{4}$ a non-internal angle and let $V_{3}$ be an internal angle

Definition: Reflex/Convex Vertex

A vertex V of a polygon is a reflex vertex if its internal angle is strictly greater than $\pi$. Otherwise the vertex is called convex.

Figure 5: Example of a polygon with convex vertex $V_{1}$ and reflex vertex $V_{2}$

Lemma 1

Every polygon must have at least one strictly convex vertex.

Proof

Order the vertices from top to bottom by their corresponding $y$ coordinates. Now, consider the lowest vertices from this list, next pick the right most vertex and suppose that such vertex is reflex. However, if the vertex was reflex then it would contradict the fact that what we have picked the right most vertex. So what we have is indeed a strictly convex vertex. qed.

Figure 6: Right most vertex must be convex

Definition: Diagonal

We say $x$ can see a point $y$ in a polygon P if the segment $x$ $y$ is fully contained in P. A diagonal then, is the line segment joining two vertices that can see each other.

Lemma 2

Every polygon P has at least one diagonal.

Proof

Let $V$ be a strictly convex vertex of a polygon P. The existence of such a vertex was established by lemma 1. Now, let a,b be vertices adjacent to $V$. if a sees b then we are done. Otherwise, vab has at least one vertex $x$ in its interior or possibly on its boundary. Take $x$ closest to $V$. Where the distance is measured perpendicular to the line ab. Suppose now we take a line parallel to ab and move it towards the interior of the polygon so that the last vertex we hit is $x$. Now $V$ $x$ must be a diagonal since there are no points from $x$ to $V$.

Figure 7: left figure denotes the case where a sees b and right shows the case where a does not see b

Figure 8: We have the diagonal vx totally inside the given polygon as we wanted

we will also need the fact that every polygon must divide the plane. Now finally we get to what will actually help us count the lattice points of an arbitrary polygon P.

theorem 1   Every simple polygon of $n$ vertices maybe partitioned into triangles by the addition of diagonals.

Proof

We will do a proof by induction on the number n $\ge$ 4 of sides of a Polygon. Let n = 4 then this is just a square where we can draw a diagonal from one vertex to the opposite vertex and we have our triangulation. Now, suppose $n > 4$. Then such Polygon P will have a diagonal by lemma 2. Pick the one that divides P into two regions. Call the left region polygon A and call the right region polygon B. Polygon B has fewer vertices than the original polygon P. Also Polygon A has fewer vertices than the original Polygon P. Now look at polygon B. Then Draw a diagonal inside B, such diagonal will partition the polygon B into yet another two regions, pick one of them and draw yet another diagonal. Repeat the same process over and over again, since the number of vertices is finite the number of available vertices that we have get smaller and smaller every time we draw a diagonal. Hence, we will eventually reach a point where the polygon B is fully triangulated. Repeat the same process for Polygon A and the original Polygon will be fully triangulated as we wanted.

Figure 9: Polygon P splits into Polygon A and B. Further, Polygon B splits into Polygons C D and E.

By the triangulation theorem, we have that we can partition a given polygon into triangles. But, how many triangles are there in a given triangulation. And remember that a triangulation will introduce an entire set of diagonals; how many diagonals are there?

Corollary

Every triangulation of a Polygon P of $n$ vertices uses $n$ - 3 diagonals and $n$ - 2 triangles.

Proof

We will proceed by induction on the number of vertices $n$. Where $n$ $\ge$ 4. So suppose $n = 4$, then we are talking about a square. Partition this square into triangles now count the number of triangles, there are exactly 4 - 2 = 2 triangles and $4 - 3 = 1$ diagonal. So for $n =$4 we have that such triangulation has $n-3$ diagonals and $n-2$ edges. Suppose now $n$ $\ge$ 4. Then for any triangulation of a Polygon P, Euler's formula $V - E - T = 1$ where V denotes the number of vertices, E denotes the number of edges, and T denotes the number of triangles. Suppose that the claim is true for some $n$ $\ge$ 4. Then Euler's formula should hold. Thus we can set

$$n - [n - 3 + n] + [n - 2] = 1$$

So now suppose this is true for $n = n + 1$. If Euler's formula still holds then we are done. So

$$[n+1]- [n + 1 - 3 + n +1] + [n +1 -2] = 1$$

So by P.M.I the conclusion follows. qed.

Now we can set up an algorithm to count the number of lattice points in a given Polygon P.

1. Triangulate P (without adding new vertices)
2. Count the number of lattice points given by each triangle, add them up then store them in a variable say R
3. Count the number of lattice points on each diagonal, add these up and subtract from R
4. Return number