Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

3 Answers

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|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.