This question is motivated by the Euclidean Traveling Salesman Problem, i.e. finding the shortest Hamiltonian path of a complete graph of N randomly placed vertices. To eliminate boundary effects I consider the problem on the unit square with periodic boundary conditions. The idea is to find a "direction" and connect points in an ordered manner along this direction to find a short path (Wheeler, J.A., On recognizing law without law, Am. J. Phys, 51(5), pp. 398, 1983).


The question is:
given N points with real coordinates on the unit square, is there a neat way to find the least-square fit line $y=rx+b \mod 1$, where $r=p/q$ is rational? The line also needs to be as short as possible. The length of the line in the square is $\sqrt{p^{2}+q^{2}}$, so minimizing the following quantity should yield a short line that passes near the points:


$\sum d\_{i}^{2}+\alpha \left( p^{2}+q^{2}\right) $.


Here $d\_{i}$ is the "distance" (vertical or perpendicular) of point i from the line and $\alpha$ is a positive weight.


By "neat" I mean something like the regular least-square line fit solution (<http://mathworld.wolfram.com/LeastSquaresFitting.html>).



Least-square fit of line with rational slope to points on a square with periodic boundary conditions
I take it that the points themselves do not have to have rational coordinates. I don't think that there would have to be a best approximation. Consider the two point set set $\{(0,0),(1,\frac{1}{\sqrt{2}})\}$. Then lines such as $y=\frac{12}{17}x$ and $y=\frac{408}{577}x$ based on convergents to $\frac{1}{\sqrt{2}}$ provide better and better approximations. Nothing changes if we use more points $(x\_i,\frac{x\_i}{\sqrt{2}})$ or use some other irrational slope.


Also, at the eight x values $\frac{\sqrt{3}-\sqrt{2}+j}{8}$ for $0 \le j \le 7$, the two functions $3x+\sqrt{2}$ and $-5x+\sqrt{3}$ are equal $\mod 1$ so either is a perfect fit.


**later** Based on some of the comments, here is one idea for a question: We are given some points $(x\_i,y\_i)$ in the unit square. For each integer $k \ge 0 $ consider all the lines $y=rx+b$ (with $r$ rational if desired, although it might be better to not make this restriction) such that $0 \le b <1$ and $k \le r <k+1$. For each such line find the squared distance to the points $(x\_i,y\_i+h\_i$ where the $h\_i$ are integers chosen to minimize each distance. QUESTION: Is there an elegant way to find the best approximating line(s) for each $k$ ? One should then also consider negative slopes. 


