Given an $n$ x $n$ integer grid, I look at all possible lines through two grid points and I am interested in the minimum distance from any grid point (not on the line) to any line.

I my guess is that the line which minimizes this distance is the one through $(0,0)$ and $(n-1,n)$ or maybe trough $(0,0)$ and $(1,n)$

My approach of computing the distances from the grid points to the ($(0,0)$ and $(n-1,n)$ ) line is not very elegant and I was wondering if someone knows a nicer approach.

(And I would still have to show that this is actually the line which minimizes the distance)

Thank you

  • $\begingroup$ Please do not sign your posts with anything, whatsoever. $\endgroup$ – user21436 Jan 18 '12 at 18:30
  • $\begingroup$ ok I just wanted to be polite, may I know why? $\endgroup$ – stefan Jan 18 '12 at 18:51
  • $\begingroup$ Please look here $\endgroup$ – user21436 Jan 18 '12 at 18:53

In order to get to the minimum distance problem quickly, we quote a formula for the distance from the point $(x_0,y_0)$ to the line with equation $px+qy+r=0$. This distance is $$\frac{|px_0+qy_0+r|}{\sqrt{p^2+q^2}}.$$ The site linked to gives a proof, as does Wikipedia. The distance from a point to a line has also been discussed more than once on StackExchange.

For our minimization problem, we can assume that one of the points is $(0,0)$, and the other is, say, $(a,b)$. So the line has equation $bx-ay=0$. We can assume that $a$ and $b$ are relatively prime, for if $d$ is their greatest common divisor, the same line is determined by $(0,0)$ and $(a/d,b/d)$.

Then by Bezout's Theorem, we can find integers $x_0$, $y_0$ between $0$ and $\max(a,b)$ such that $|bx_0-ay_0|=1$. Thus the smallest non-zero value of $|bx-ay|$ as $(x,y)$ ranges over our grid is $1$.

So the minimum possible non-zero distance from a gridpoint to our line is $\dfrac{1}{\sqrt{a^2+b^2}}$.

Now we want to maximize $a^2+b^2$, as $(a,b)$ ranges over relatively prime pairs on our grid. Then for fixed $a+b$, this maximum occurs when $a$ and $b$ differ by as little as possible. If $n=1$, the maximum value of $\sqrt{a^2+b^2}$ is achieved when $a=b=1$.

Suppose now that $n>1$. Then the maximum value of $a^2+b^2$, given that $\gcd(a,b)=1$ and $(a,b)$ is on our grid is attained at $a=n-1$, $b=n$, and at $a=n$, $b=n-1$. The minimum non-zero distance is therefore $$\frac{1}{\sqrt{2n^2-2n+1}}.$$

Comment: For our particular problem, we do not need Bezout's Theorem, since if $n>1$ then the distance from $(1,1)$ to the line through $(0,0)$ and $(n-1,n)$ is $1/(2n^2-2n+1)$. It is clear that we can't do better, since $|bx_0-ay_0|$ is at least $1$. However, if the $n\times n$ grid is replaced by an $m\times n$ grid, the natural analysis uses Bezout's Theorem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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