Lattice points close to a line

Question

Take a sheet of grid paper and draw a straight line in any direction from the origin. What is the closest non-zero grid point $\boldsymbol{p}\in\mathbb{Z}^2$ within a distance $\epsilon>0$ of the line?

I have been unable to construct an example where the distance is large for any $\epsilon$. I would like to prove the following:

$\forall \epsilon>0 ~~ \exists R>0 ~~ \forall \boldsymbol{v} \in \mathbb{R}^2 ~~ \exists\boldsymbol{q}\in\mathbb{Z}^2, \|\boldsymbol{q}\| < R$ such that:

$\frac{|p_x v_y - p_y v_x|}{\|\boldsymbol{v}\|}<\epsilon$

where the LHS is the point-line distance.

Answer 1

The statement that you want to prove follows from Dirichlet's Theorem, which says that for any real number $\alpha$ and for any positive integer $Q$, there is a fraction $a/q$ with $|q|\le Q$ such that $$|\alpha-a/q|\le 1/q(Q+1).$$ Here $\alpha$ is the slope of your line and $Q$ is playing the role of $R$, with $1/(Q+1)$ playing the role of $\epsilon$. Of course in your problem the actual numerical value of $R$ as a function of $\epsilon$ depends, up to a constant, on what norms you are using. Also technically, to make the connection clearer, you should choose $\alpha$ to be the slope of the line or its reciprocal, whichever is smaller.

For a paticular choice of $\mathbf{v}$ the fastest way to actually find the best integer vectors, as Igor pointed out, is by using the continued fraction algorithm. If you understand the connection to Dirichlet's Theorem then it should be clear how to do this.

Answer 2

The key words to look for is "continued fractions" and "Bresenham". See http://www.cs.tau.ac.il/~nachum/calendar-book/papers/bresenham.pdf

Answer 3

If the slope of the line is rational (say, $ \frac{p}{q} $), then it will exactly intersect the point $(q,p)$.

If the slope of the line is irrational, then the induced image of the line in the quotient space $\mathbb{R}^2 / \mathbb{Z}^2$ (flat torus) is dense. Because the preimage of the "corner" of the flat torus (this is only one point) is the lattice points $\mathbb{Z}^2$ in $\mathbb{R}^2$, the original line (in $\mathbb{R}^2$) will pass arbitrarily close to some nonzero lattice point. This only gives an existence argument, not a constructive answer.

See http://www.cut-the-knot.org/do_you_know/shredding.shtml for a high-level discussion and some possibly useful pictures.