Home » Blog » Prove a formula for the area of a polygon whose vertices are lattice points

Prove a formula for the area of a polygon whose vertices are lattice points

by RoRi

Recall, a lattice point in the plane is a point with integer coordinates. Then, we look to establish a formula for the area of the polygon,

    \[ a(P) = I + \frac{1}{2}B - 1, \]

where I is the number of lattice points inside of P, and B is the number of lattice points on the boundary.

  1. Prove the formula holds for rectangles whose sides are parallel to the axes.
  2. Extend the result to right triangles and parallelograms whose vertices lie on lattice points.
  3. Prove that the formula holds for general polygons.
  1. Proof. Let R be an h \times k rectangle with sides parallel to the coordinate axes. Then, R is measurable (since it is a rectangle) and a(R) = hk.
    Next, since the vertices are on lattice points, B = 2(h+1) + 2(k+1) - 4 and I = (h-1)(k-1). Thus,

        \begin{align*} I + \frac{1}{2}B - 1 &= (h-1)(k-1) + \frac{1}{2}(2(h+1) + 2(k+1) -4) - 1 \\ &= hk - h -k + 1 + h + 1 + k +1 - 2 - 1 \\ &= hk. \qquad \blacksquare \end{align*}

  2. Proof. We know that any right triangle can be enclosed in a rectangle with edges whose lengths are equal to the lengths of the legs of the right triangle. Further, this rectangle is composed of two congruent right triangles joined along its diagonal. These right triangles each have area one half that of the rectangle and intersect along the diagonal (which has zero area (1.7, #1) since it is a line in the plane). Given a right triangle T, let R be such a rectangle, and let S be the right triangle that makes up the other half of R, so S \cup T \cong R.
    Since R is a rectangle we know by part (a) that

        \[ a(R) = I_R + \frac{1}{2} B_R - 1. \]

    Further, any interior point of R will be an interior point of either S or T, or will lie on their shared boundary. Thus,

        \[ I_R = I_S + I_T + H_P, \]

    where H_P denotes the points on the (shared) hypotenuse of the two right triangles. Then, we also have for the boundary points,

        \[ B_R = B_S + B_T - 2 - 2H_P. \]

    Finally, since S and T are congruent, we know B_S = B_T and I_S = I_T. So, putting this all together, we have,

        \begin{align*} a(R) &= I_R + \frac{1}{2} B_R -1\\ &= 2I_S + H_P + \frac{1}{2} (2B_S - 2 - 2H_P) - 1 \\ &= 2(I_S + \frac{1}{2}B_S - 1) \end{align*}

    or,

        \[ I_S + \frac{1}{2} B_S - 1 = \frac{1}{2} a(R). \]

    But, we know \frac{1}{2} a(R) = a(S); thus,

        \[ a(S) = I_S + \frac{1}{2}B_S -1. \]

    This proves the result for right triangles with vertices on lattice points. \qquad \blacksquare

    Now, for a parallelogram with vertices on lattice points, we prove that the union of two simple polygons along a single edge gives a polygon for which the formula holds if it holds for the components (since then the parallelogram can be considered as a union of right triangle and rectangles, for which we have already established that the formula holds).
    Proof. Let S and T be polygons for which the formula holds. Then,

        \[ a(S) = I_S + \frac{1}{2}B_S - 1 \qquad \text{and} \qquad a(T) = I_T + \frac{1}{2} B_T - 1. \]

    Further, any interior point of S or T will be an interior point of S \cup T. Any new interior point, I_n, must have previously been a boundary point of both S and T. Thus, we have the following:

        \[ I_{S \cup T} = I_S + I_T + I_N \qquad B_{S \cup T} = B_S + B_T - 2I_N - 2. \]

    (Where the -2 is to account for the end points of the joined edge.) Thus,

        \begin{align*} I_{S \cup T} + \frac{1}{2}B_{S \cup T} -1 &= I_S + I_T + I_N + \frac{1}{2} B_S + \frac{1}{2}B_T - I_N - 1 -1 \\ &= I_S + \frac{1}{2} B_S -1 + I_T + \frac{1}{2}B_T - 1 \\ &=a(S) + a(T) \\ &= a (S \cup T). \end{align*}

    Hence, the formula holds for S \cup T if it holds for S and T. Thus, it holds for all parallelograms, as the union of right triangles and rectangles. \qquad \blacksquare

  3. Proof. We already have this from part (b) since we can realize any simple polygon as the union of finitely many right triangles (i.e., every simple polygon is triangularizable). \qquad \blacksquare

4 comments

    • PseudonymousAJ says:

      0 to h gives you h+1 lattice points per side, 0 to k gives you k+1 lattice points per side. a pair of sides of length k and length h make up the boundary of the rectangle. therefore 2(h+1)+2(k+1). however, here, we have counted each corner twice (once from h length side and once from k length side), therefore we subtract 4.

  2. jamiehlusko says:

    Your answer assumes that 2 of the right triangle’s sides are parallel to the coordinate axis, but this is not specified in the question. For example consider the lattice right triange (0,0), (1,1), (2, 0).

    • Camilo Diaz says:

      By construction you can fit a triangle (in this case a right one) between the parallels lines that determinate them. And then you have a region with the same area, being the right triangle we know how to calculate.

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):