1
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I'm confused by the question. Do you want the line to go through the square $k$ times, where $k$ is the denominator of $r$, and have the line pass near all the points? If that's what you want, how do you control for $k$ (as increasing it will presumably give you better and better solutions). Maybe you want the best fit with $r$ having numerator and denominator less than $n$. $\endgroup$
    – Peter Shor
    Oct 18, 2010 at 3:15
  • $\begingroup$ I echo Peter Shor's confusion. What do you want if $N=2$ and the line through the two points has irrational slope? There are rational lines arbitrarily close to that irrational line. It may be that what you are looking at is the diophantine approximation problem called simultaneous approximation, in which case there is a considerable literature. But we shouldn't have to read your mind. $\endgroup$
    – Gerry Myerson
    Oct 18, 2010 at 3:53
  • $\begingroup$ Let me explain more carefully what I think you might want (based on your motivation). Join opposite sides of the unit square to make a torus. A line with slope $r=p/q$ is going to pass through the square (torus) $q$ times horizontally and $p$ times vertically before finally meeting up with itself. Question: given $t$, is there a good way to find (or approximately find) the line with $p,q \leq t$ which minimizes the least-squares distance to all the points. By working on a torus, I expect you've given up convexity, which means the best line is probably going to be really difficult to find. $\endgroup$
    – Peter Shor
    Oct 18, 2010 at 4:40
  • $\begingroup$ Thanks for the comments. I edited the entry to clarify the question. $\endgroup$
    – Tamas Kalmar-Nagy
    Oct 18, 2010 at 5:07
  • $\begingroup$ I think the answer will display sensitive dependence on $\alpha$. E.g., if $N=3$ and $\alpha=1,000,000$, then no doubt the minimizing line will be of the form $y=b$. $\endgroup$
    – Gerry Myerson
    Oct 18, 2010 at 5:19

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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