

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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.

share|cite|improve this question
Presumably $v_x$ and $v_y$ are the components of $\boldsymbol{v}$, and $p_x$ and $p_y$ are the components of $\boldsymbol{q}$. – Gerry Myerson Dec 12 '11 at 21:41
up vote 6 down vote accepted

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.

share|cite|improve this answer

The key words to look for is "continued fractions" and "Bresenham". See

share|cite|improve this answer

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 for a high-level discussion and some possibly useful pictures.

share|cite|improve this answer

Your Answer


