3
$\begingroup$

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

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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