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,
where is the number of lattice points inside of
, and
is the number of lattice points on the boundary.
- Prove the formula holds for rectangles whose sides are parallel to the axes.
- Extend the result to right triangles and parallelograms whose vertices lie on lattice points.
- Prove that the formula holds for general polygons.
-
Proof. Let
be an
rectangle with sides parallel to the coordinate axes. Then,
is measurable (since it is a rectangle) and
.
Next, since the vertices are on lattice points,and
. Thus,
-
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
, let
be such a rectangle, and let
be the right triangle that makes up the other half of
, so
.
Sinceis a rectangle we know by part (a) that
Further, any interior point of
will be an interior point of either
or
, or will lie on their shared boundary. Thus,
where
denotes the points on the (shared) hypotenuse of the two right triangles. Then, we also have for the boundary points,
Finally, since
and
are congruent, we know
and
. So, putting this all together, we have,
or,
But, we know
; thus,
This proves the result for right triangles with vertices on lattice points
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. Letand
be polygons for which the formula holds. Then,
Further, any interior point of
or
will be an interior point of
. Any new interior point,
, must have previously been a boundary point of both
and
. Thus, we have the following:
(Where the
is to account for the end points of the joined edge.) Thus,
Hence, the formula holds for
if it holds for
and
. Thus, it holds for all parallelograms, as the union of right triangles and rectangles
-
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)
Where did you came up with B = 2(h+1) + 2(k+1) – 4 and I = (h-1)(k-1) in the first proof?
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.
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).
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.