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.

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$. $\endgroup$ – Noam D. Elkies Aug 17 '13 at 6:03