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:

Let $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:

Let $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:

Let $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”:

Theorem: 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}$