# Finding integer points inside of a parallelogram

Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point with integer coordinates in the interior of $P$, though there are possibly many such points. I would like to find one of these points; ideally, a solution to finding such a point would not depend on knowing that one exists.

To reformulate (my lines will not generally be vertical), I want to find an integer solution $(x,y)$ to the equations \begin{eqnarray*} y &<& ax + b_1, \\ y &>& ax + b_2, \\ y &<& cx + b_3, \\ y &>& cx + b_4. \end{eqnarray*}

Is there a good way to tackle such a problem? Note that this can be an arbitrarily bad situation, such as having the parallelogram containing a small neighborhood of the line segment from $(0,0)$ to $(2^{107}-1,2^{127}-1)$, and such that many points are closer to the boundary lines than either of the two interior integral points.

• This is a typical setting for lattice basis reduction (which in 2D is closely related to the Euclidean algorithm applied to $1$ and the slope of the parallelogram's longer edge, and to that slope's continued-fraction development). Apply a linear transformation $T$ taking the parallelogram to a unit square $S$, and ${\bf Z}^2$ to some lattice $L$. Find a reduced basis for $L$. It is then easy (assuming no precision issues with a point of $L$ coming very close to the boundary of $S$) to decide whether $S \cap L$ contains some point $p$, and if yes to find such $p$. Then recover $T^{-1}p$. – Noam D. Elkies Aug 17 '13 at 6:03
• @Noam Elkies: Thank you; I wasn't sure what terms to look for, but that seems like enough to solve my problem. – Eric Tressler Aug 17 '13 at 6:08
• @Noam and Eric: If Noam Elkies' comment answers the question, may I suggest that Noam repost it as an answer? – Ricardo Andrade Aug 17 '13 at 9:57