5
$\begingroup$

Given an $n \times n$ grid, what is the minimum angle between any two distinct lines, each going through some grid point $p$ and at least one other grid point?

My guess is the minimum is attained by the line through $(0,0), (n,1)$ and the line through $(0,0), (n,0)$ but how can I show that this is the optimal line pair?

  • 0
    "The least angle in a triangle is the angle opposite to the smallest side" will be one lemma you'll have to crucially use.2012-02-21
  • 1
    The sine of the angle is the determinant of the two directional vectors divided by the product of their lengths. So look for vectors with determinant one and a large product of their lengths. (Partial) convergents of the golden ratio come to mind. These appear in the Fibonacci sequence 1, 1, 2, 3, 5, 8, ... For example the angle between (3,5) and (5,8) is smaller than that between (1,1) and (10,9). Not sure if you can do better than that.2012-02-21
  • 0
    Another line of attack (though I'm not sure how fruitful): We know $\cos (\theta) = \frac{\vec{a} \cdot \vec{b}}{\| a \| \| b \|}$. So, If you know calculus (and Lagrange multipliers in particular), then it is enough to maximize the function $$f(x,y,z,w) = \frac{xz + yw}{(x^2 + y^2)(x^2 + w^2)}$$ subject to $x,y,z,w \in \{0 , \dots , n\}$.2012-02-21
  • 0
    My guess is the pair $(0,0);(n-1,n)$ , $(0,0);(n,n)$ I think it may be tried for induction!2012-02-21
  • 1
    no (n-1, n) and (n-2, n-1) are certainly better, possibly optimal.2012-02-21
  • 0
    Well $$\cos \theta= \frac{pq+rs}{\sqrt{(p^2+q^2)(r^2+s^2)}}$$ we should maximize the square of this function. Where we suppose that $p,q,r,s\geq 0$ are integers.2012-02-21

2 Answers 2

4

I think the smallest angle is between lines $(0,0)-(n-1, n)$ and $(0,0) - (n-2,n-1)$. For these two directional vectors we have

$$ \det \begin{pmatrix} n-1 & n-2 \\ n & n-1 \end{pmatrix} = 1 $$

and so for the angle $\alpha$ we have

$$ \sin(\alpha) = \frac{1}{||(n-1, n)|| \cdot ||(n-2, n-1)||} < \frac{1}{2(n-1)^2}. $$

Among all the vectors in the grid, only the following are longer than $(n-2, n-1)$:

$$ (n-3,n), (n, n-3), (n-2, n), (n, n-2), (n-1, n), (n, n-1), (n-1, n-1), (n,n) $$

The pair given above has the smallest (positive) angle in this set.

3

That is not the optimal pair.

Compare the angle between the lines through $(0,0),(4,1)$ and $(0,0),(4,0)$ [about $14^\circ$] with the angle between the lines through $(0,0),(4,3)$ and $(0,0),(3,2)$ [about $3.2^\circ$].

  • 0
    right. Lines (0,0)-(n-2, n-1) and (0,0)-(n-1, n) form a good candidate pair for the smallest angle for any n. see my comment about sine of the angle above.2012-02-21