2
$\begingroup$

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.

picture of integer lattice in the plane, and of thin diagonal rectangle with a single distinguished lattice point within

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ 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$. $\endgroup$
    – Noam D. Elkies
    Commented Aug 17, 2013 at 6:03
  • $\begingroup$ @Noam Elkies: Thank you; I wasn't sure what terms to look for, but that seems like enough to solve my problem. $\endgroup$
    – Eric Tressler
    Commented Aug 17, 2013 at 6:08
  • $\begingroup$ @Noam and Eric: If Noam Elkies' comment answers the question, may I suggest that Noam repost it as an answer? $\endgroup$
    – Ricardo Andrade
    Commented Aug 17, 2013 at 9:57

1 Answer 1

Reset to default
1
$\begingroup$

You can try to apply the algorithm from the paper

B. N. Delone, “An algorithm for the “divided cells” of a lattice”, Izv. Akad. Nauk SSSR Ser. Mat., 11:6 (1947), 505–538

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .