\chapter{CONVEXITY POLYGONS} % MUST be CAPITALIZED
\section{Continued Fractions}
A continued fraction of \hbox{type II} representation (henceforth
referred to as a \hbox{CF II}) of a positive real number is one of the
form
%$$b_{0}-{1\hfill\over\displaystyle
%b_{1}-{\strut 1\hfill\over\displaystyle
%b_{2}-{\strut 1\hfill\over\displaystyle b_{3}-\ldots}}}$$
% OR, TYPESET DIFFERENTLY USING AmS\LaTeX command continued fraction
% command \cfrac
$$b_{0}-\cfrac{1}{b_{1}-\cfrac{1}{b_{2}-\cfrac{1}{b_{3} - \ldots}}}$$
which we will denote by $$[[b_{0};b_{1},b_{2},b_{3}\ldots]].$$ Given
the sequence of partial quotients of the continued fraction, $[[b_0;
b_1, \ldots]]$, we may calculate the numerator, $p_i$, and
denominator, $q_i$, of its $i$th convergent by the following
iteration:
\begin{eqnarray}
p_{-1} = 0 &\quad& q_{-1} = -1 \label{eq: minus1}\\ p_{0} = 1
&\quad& q_{0} = 0 \label{eq: zero}
\end{eqnarray}
\begin{equation}
p_{i}=b_{i-1}p_{i-1}-p_{i-2} \label{eq: nextp}
\end{equation}
\begin{equation}
q_{i} = b_{i-1}q_{i-1}-q_{i-2}. \label{eq: nextq}
\end{equation}
We state, without proof, the properties of the convergents that follow
from this construction. These properties are used traditionally to
prove that the sequence of convergents from the \hbox{CF II} of any
real number must converge to that number. The proofs of the
individual statements are simple induction.
\begin{lemma}\label{lem: Properties} Given the sequence, $\{p_i\colon
i\geq -1\}$ and $\{q_i\colon i \geq -1\}$ defined by equations
~\ref{eq: minus1} through ~\ref{eq: nextq}, based on the sequence of
positive integers, $\{b_i: i \geq 0\}$, then, for $i \geq 1$, we
have
\begin{eqnarray}
&p_i \geq p_{i-1} > 0;\quad q_i > q_{i-1} \geq 0;& \label{eq:
increasing}\\ &p_{i-1}q_{i} - p_{i}q_{i-1} = 1; \quad
\hbox{gcd}(p_i,q_i) = 1;& \label{eq: relprime}\\ & \frac{p_1}{q_1} >
\frac{p_2}{q_2} > \frac{p_3}{q_3} > \ldots;&
\label{eq: fromabove}\\
&\frac{p_i}{q_i} = [[b_0;b_1,\ldots,b_{i-1}]]&;
\label{eq: ithterm}
\end{eqnarray}
%
%
\end{lemma}
\section{Convergent points in the integer lattice}
\begin{lemma}Let $P= (n,m)$ be a totally positive lattice point of
slope $$\frac{m}{n} = [b_0; b_1, \ldots, b_k]$$ and let $$C_{-1}, C_0,
C_1, \ldots, C_{k+1}$$ be the convergent points of $P$. Then, the
final convergent, $C_{k+1}$ and $P$, when considered as vectors, are
parallel and $$P= dC_{k+1},$$ where $d$ is the greatest common divisor
of $m$ and $n$, the coordinates of $P$.
\end{lemma}
\begin{proof} By equations~\ref{eq: nextp} and~\ref{eq: nextq}, the
coordinates of the $i$th convergent point, $C_i$ are the numerator
and denominator of the $i$th convergent, i.e., $$\frac{p_i}{q_i} =
[[b_0;b_1, \ldots, b_{i-1}]] \Longrightarrow C_i = (q_i,
p_i).$$Furthermore, by equations ~\ref{eq: relprime} and ~\ref{eq:
ithterm},
$$\frac{m}{n} = \frac{p_{k+1}}{q_{k+1}},$$ and the coordinates of
$C_{k+1}=(q_{k+1}, p_{k+1})$ are relatively prime.
\end{proof}
\begin{theorem}\label{th: Gen}Let $P = (n, m)$ be a totally positive
point of $\cL$, with $m$ and $n$ relatively prime and let $$C_{-1},
C_0, C_1, \ldots, C_{k+1}$$ be the convergent points of $P$. A
positively oriented basis for the lattice $\cL$ may be constructed
using the point $P$ as the first of an ordered pair of lattice
points, as such: $$\cL=[P,G] \Longleftrightarrow G = C_k + iP \quad
i \in \Z$$
\end{theorem}
\begin{corollary}\label{Cor: Coll}For any totally positive point $P = (n,m)$ in the
integer lattice $\cL$, where $m$ and $n$ are relatively prime, the
following are equivalent:
\begin{tabbing}
$\qquad$ \= $(i) \quad$ \= There are no lattice points in the
interior of $\D O\e_2P$\\ \> $(ii)$ \> $\frac{m}{n} =
[[b_0;b_1,\ldots,b_{d-1}]] \quad $, where\\ \> \>$d\geq 1 \qquad b_0
\geq 1 \quad b_i = 2 \quad 0 < i \leq d $\\ \> $(iii)$ \> $P =(d,
pd+1) \quad \hbox{where} \quad d>0 \quad p \geq 0$
\end{tabbing}
\end{corollary}
\begin{proof}
\noindent $[(i) \Longleftrightarrow (ii)]$ : Since $m$ and $n$ are
relatively prime, there are no lattice points on the line segment
$\overline{OP}$. Thus, $P$ is its own final convergent. Clearly
there are no lattice points on $\overline{O\e_1}$.
\noindent $[(ii) \Longleftrightarrow (iii)]:$ This can be verified by
calculating the continued fraction directly, where $b_0 = p-1$.
\end{proof}
Thus, we can recognize from the continued fraction if the convergents
will align on the segment $\overline{\e_1,P}$. Figure ~\ref{fig:
Coll} shows an example of such a convexity polygon, $\G_O(P, \e_2)$,
where $P = (6,6p+1)$, for some non-negative integer, $p$. There are
no lattice points interior to the triangle, $\D O \e_2 P$, but there
are five collinear points interior to the edge, $\overline{\e_2P}$.
\begin{figure}
\setlength{\unitlength}{.025in}
\begin{picture}(155,170)(-25,0)
\put(0,0){\vector(0,1){170}}
\put(0,0){\vector(1,0){130}}
\thicklines
\put(0,0){\line(3,4){120}}
\put(0,0){\circle{3}}
\put(120,160){\circle*{3}}
\put(125,160){$P$}
\put(100,140){\circle*{3}}
\put(80,120){\circle*{3}}
\put(60,100){\circle*{3}}
\put(40,80){\circle*{3}}
\put(20,60){\circle*{3}}
\put(0,40){\circle*{3}}
\put(0,80){\circle*{3}}
\put(0,120){\circle*{3}}
\put(0,160){\circle*{3}}
\put(-10,40){$\e_2$}
\put(0,40){\line(1,1){120}}
\end{picture}
\caption{$\G_{O}(P, \e_2)$, where $P = (6,6p+1)$}
\label{fig: Coll}
\end{figure}
By equation ~\ref{eq: increasing} of Lemma ~\ref{lem: Properties}, the
first coordinates of the convergent points to $P$ are strictly
increasing,
$$0 = C_0^{(1)} < 1 = C_1^{(1)} < C_2^{(1)}< \ldots< C_{k+1}^{(1)}.$$
Therefore, there is exactly one convergent, $C_i$, where $i < k$, for
which we have $$C_i^{(1)} \leq (E- G_m)^{(1)} < C_{i+1}^{(1)}.$$ We
claim that $G_{m+1} = G_m + C_i$.
If $E^{(1)}-G_{m+n}^{(1)} > 0$ then all of the conditions for the
original triangle, $\D O \w E$, apply to the smaller triangle, $\D E
\tau G_{m+n}$:
\begin{enumerate}
\item{The slope of $\tau - G_{m+n}$ is the same as that of a totally
positive lattice point, $C_i$;}
\item{We know all of the convergent points to $C_i$;}
\item{The segment $\overline{\tau E}$ is vertical; and}
\item{$G_{m+n}$ and $E$ are lattice points, but $\tau$ may not be.}
\end{enumerate}
\subsection{The First and the Last Convergent}
If we were to assume that the rational element is greater than 1, then
there would be no elements of ${\cal M}$ on the segments
$\overline{O{\bf 1}}$ or $\overline{O\ef}$. In terms of the
algorithm, the list of convergent points that might be tested would be
restricted to $\{C_1, \ldots, C_k\}$, rather than $\{C_0, \ldots,
C_{k+1} \}$.
\subsection{Choosing More Than Once}
Rather than repeatedly testing the same convergent point in the
algorithm, we can choose all collinear points simultaneously.
We will use the fact that the number of convergents in the \hbox{CF I}
is logarithmic to prove the timing of the algorithm. Therefore, we
need a means of comparing the \hbox{CF I} expression to a \hbox{CF
II}. Stark provided a simple proof of the conversion in one of a
series of lectures he gave at MIT. One can convert a \hbox{CF I} into
a \hbox{CF II} (and vice-versa) as follows:
If $n$ is even, then
$$[a_0; a_1, \ldots, a_n] = [[a_0 + 1;\underbrace{2,2,\ldots,
2}_{a_1-1 \hbox{times}}, a_2+2, \underbrace{2,2,\ldots,2}_{a_3-1
\hbox{times}}, a_4+2, \ldots, a_n+1]] $$
If $n$ is odd, then
$$[a_0; a_1, \ldots,a_n] = [[a_0 + 1;\underbrace{2,2,\ldots, 2}_{a_1-1
\hbox{times}}, a_2+2, \ldots, \underbrace{2,2,\ldots, 2}_{a_n-1
\hbox{times}}]].$$