Theorem: (Pick) Let P \subset \mathbb{R}^2 be a simple polygon whose vertices are in \mathbb{Z}^2. Let i (resp. b) denote the cardinality of \mathrm{int}(P) \cap \mathbb{Z}^2 (resp. of \partial P \cap \mathbb{Z}^2). Then the area A(P) of P is given by the formula

\displaystyle A(P)= i + \frac{b}{2}-1.

Proof. We first prove the theorem in specific cases.

  • Pick’s formula is true for rectangles:

Let P be a x \times y rectangle whose vertices are in \mathbb{Z}^2. Then i=(y-1)(x-1) and b=2(x+y), hence

\displaystyle i+ \frac{b}{2} -1 = xy = A(P).

  • Pick’s formula is true for right triangles with a vertical edge:

Case 1Let R be the x \times y rectangle P \cup Q and let c denote the cardinality of \partial P \cap \partial Q \cap \mathbb{Z}^2. Then i= \frac{(y-1)(x-1)-c+2}{2} and b=c+x+y-1 hence

\displaystyle i + \frac{b}{2}-1= \frac{xy}{2}= A(P).

The same argument applies to other kind of right triangles with a vertical edge (like Q for example).

  • Pick’s formula is true for such triangle:

Case 2Let C be the rectangle P \cup R \cup S \cup T. Let r denote the cardinality of \partial P \cap \partial R \cap \mathbb{Z}^2; s and t are defined in the same way. Then i=i_C-(i_S+i_T+i_R)-(r+s+t-3)+3 and b=b_T+b_R+b_S-b_C=r+s+t-3, hence using the previous cases:

\begin{array}{ll} \displaystyle i+ \frac{b}{2} - 1 & \displaystyle = \left( i_C+ \frac{b_C}{2}-1 \right)- \left( i_R+ \frac{b_R}{2}-1 \right)- \left(i_S + \frac{b_C}{2}-1 \right)- \left( i_T+ \frac{b_T}{2}-1 \right) \\ \\ & =A(C)-A(R)-A(S)-A(T)=A(P) \end{array}

  • Pick formula is true for such triangle:

Case 3Let C be the rectangle P \cup R \cup S \cup T \cup U. Let r denote the cardinality of \partial P \cap \partial R \cap \mathbb{Z}^2; s and t are defined in the same way. Let u (resp. v) be the cardinality of \partial U \cap \partial T \cap \mathbb{Z}^2 (resp. \partial U \cap \partial R \cap \mathbb{Z}^2). Then i= i_C-i_R-i_S-i_T-i_U-(r+s+t+u+v-3)+6 and b=r+s+t-3=b_R+b_S+b_T+b_U-b_C-2(u+v)+4. Exactly like the previous case, we deduce

\displaystyle i+ \frac{b}{2}-1= A(C)-A(R)-A(S)-A(T)-A(U)=A(P).

Finally, we deduce that Pick’s formula is true for all triangle (whose vertices are in \mathbb{Z}^2).

Now, we show our theorem by induction on the number n of vertices of P. If n=3, P is a triangle and we already proved that Pick’s theorem holds in this case. Suppose that the theorem holds for every polygon with \leq n vertices and suppose that P has n+1 vertices. Using the following lemma:

Lemma: Let P \subset \mathbb{R}^2 be a polygon. Then P contains a diagonal, that is edge between two vertices lying in the interior of P.

to decompose P as the union of two polygons P_1 and P_2 whose intersection is an edge. Let c denote the cardinality of \partial P_1 \cap \partial P_2 \cap \mathbb{Z}^2. Now i=i_1+i_2+c-2 and b=b_1+b_2-2c+2, so using our induction hypothesis:

\displaystyle i+ \frac{b}{2}-1= \left(i_1+ \frac{b_1}{2}-1 \right) + \left( i_2+ \frac{b_2}{2}-1 \right)= A(P_1)+A(P_2)=A(P).

Therefore, our proof by induction is completed. \square

Proof of the lemma: Let P be a simple polygon. First, we prove P has an angle smaller than \pi.

For c \in \mathbb{R}, let d_c be the line y=c; let D_c denote the upper closed half-space determined by d_c. Because P is compact, r= \inf \{c \in \mathbb{R} \mid P \subset D_c\} is well-defined and d_r \cap P \neq \emptyset.

If d_r \cap P contains a vertex v then the angle of P at v cannot be greater than \pi, otherwise P would have a point below d_r. If d_r \cap P contains an edge [t,s] then the angles of P at t and s cannot be greater than \pi, otherwise P would have a point below d_r.

Therefore, P has an angle smaller than \pi at some vertex A. Let B and C denote the two vertices of P adjacent to A.

If [B,C] lies in the interior of P, then [B,C] is a diagonal. Otherwise, the triangle ABC contains a finite number of vertices X_1,\dots,X_m of P. Let D be the bisectrix of the angle \widehat{BAC} and, for each 1 \leq i \leq m, let D_i be the line perpendicular to D passing through X_i.

Let 1 \leq k \leq m be such that d(A,D_k)= \min\limits_{1 \leq i \leq m} d(A,D_i). In particular, D_k separates A and the X_i, so [A,X_k] is a diagonal. \square

Corollary 1: At least one vertex of an equilateral triangle has a non-integer coordinate.

Proof. Suppose by contradiction that there exists an equilateral triangle T whose vertices are in \mathbb{Z}^2. Then

\displaystyle A(T)= i+ \frac{b}{2}-1 \in \mathbb{Q}.

On the other hand, the length of the edges of T is \alpha= \sqrt{a^2+b^2} for some a,b \in \mathbb{Z}, hence

\displaystyle A(T)= \frac{\alpha^2}{2} \sin \left( \frac{\pi}{3} \right) = \frac{a^2+b^2}{4} \cdot \sqrt{3} \in \mathbb{Q}( \sqrt{3}).

Therefore, A(T) \in \mathbb{Q}(\sqrt{3}) \cap \mathbb{Q} = \mathbb{Q} that is a=b=0: a contradiction. \square

Corollary 2: An n \times n square is randomly tossed onto an integer grid. Then it may never cover more than (n+1)^2 grid points.

Proof. First, notice that b \leq 4n where 4n is the perimeter of the square. Then, the square covers

\displaystyle i+b = \left(i+ \frac{b}{2}-1\right) + \frac{b}{2}+1 \leq n^2+2n+1=(n+1)^2

grid points, according to Pick’s theorem. \square

Definition: Let F_m= \{ \frac{a}{b} \mid a \wedge b=1, \ b \leq m \} \subset \mathbb{Q}_{>0}. The sequence obtained by ordering F_m is called the Farey sequence of order m.

For example, the beginning of the Farey sequence of order three is

\displaystyle \frac{1}{3} < \frac{1}{2} < \frac{2}{3} < \frac{1}{1} < \frac{4}{3} < \frac{2}{1}< \frac{4}{1} < \cdots

Corollary 3: Let \frac{a}{b} < \frac{c}{d} be two consecutive terms in a Farey sequence. Then bc-ad=1.

This fact has been already noticed and proved by the French mathematician Augustin Cauchy in Démonstration d’un théorème curieux sur les nombres (Proof of a curious theorem about numbers). Surprisingly, this theorem has a geometric interpretation and can be proved using Pick’s theorem:

Proof. Let \frac{a}{b} < \frac{c}{d} be two consecutive terms in the Farey sequence of order m.

Let \mathcal{D}_m the set of lines passing through the origin and meeting \{-m, \dots, m \} \times \mathbb{Z}. If d,d' \in \mathcal{D}_m, we say that d \prec d' if the gradient of d' is greater than the gradient of d. Ordering \mathcal{D}_m with respect to \prec, we get a sequence d_1,d_2, \dots of lines.

For each n \geq 1, let (x_n,y_n) be the closest point of d_n \cap \{-m, \dots, m\} \times \mathbb{N} to (0,0). Then \frac{y_n}{x_n} is the n-th term of the Farey sequence of order m.

Let A=(b,a), B=(d,c) and T=AOB. Now we compute the area of T using Pick’s theorem.

Because the fractions \frac{a}{b} and \frac{c}{d} are irreducible, the open segments (OA) and (OB) do not meet \mathbb{Z}^2. If AB or \mathrm{int}(T) meeted \mathbb{Z} there would be a line d \in \mathcal{D}_m such that (OB) \prec d \prec (OA), that is \frac{a}{b} and \frac{c}{d} would not be consecutive in the Farey sequence. Therefore, A(T)=0+ \frac{3}{2}-1= \frac{1}{2} according to Pick’s theorem.

On the other hand, A(T)= \frac{1}{2} \left| \begin{matrix} b & d \\ a & c \end{matrix} \right|= \frac{1}{2}(bc-ad), hence bc-ad=1. \square

To conclude our note, we prove a more general formula when the polygon has “holes”:

fig4Theorem: Let Q and P_1, \dots, P_n \subset \mathrm{int}(Q) be simple polygons. Let P denote the “holed polygon” Q \backslash \bigcup\limits_{k=1}^n \mathcal{int}(P_i). Then the area A(P) of P is given by

\displaystyle A(P)= i+ \frac{b}{2}+n-1,

Proof. First, notice that

\displaystyle i= i_Q- \sum\limits_{k=1}^n i_k- \sum\limits_{k=1}^n b_k \ \text{and} \ b=b_Q+ \sum\limits_{k=1}^n b_k.

Then, using Pick’s theorem:

\begin{array}{ll} A(P) & =A(Q)- \sum\limits_{k=1}^n A(P_i) \\ \\ & \displaystyle = \left(i_Q+ \frac{b_Q}{2}-1 \right)- \sum\limits_{k=1}^n \left(i_k + \frac{b_k}{2}-1 \right) \\ \\ & \displaystyle = i + \frac{b}{2}+n-1 \hspace{1cm} \square \end{array}

Advertisements