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