# Fitting two parallel lines to a set of points

In two dimension I have a set of points X = $\{x_1,..., x_N\}$. I want to fit two parallel lines to these points like $l_1$ and $l_2$ $$l_1 = p_1 + \lambda n^\perp$$ $$l_2 = p_2 + \lambda n^\perp$$ $$n^Tn=1$$

How can I solve such a problem analytically or approximately for a given importance weighting $w_i$'s.

$$\arg \max_{n,p_1,p_2} \sum_{i=1}^{N}w_i\min \left( \lVert(p_1-x_i)^Tn\rVert, \lVert(p_2-x_i)^Tn\rVert \right)$$

Note: The distances of points to lines are written in Euclidean norm for ease but it is not a constraint.

• As an approximation I think of replacing $\min(a,b)$ with $ab/(a+b)$ but can not reach to a point. – xonobo Sep 19 '15 at 10:44

The difficult part in this sort of fit is assigning the points to the two lines – such assigments can often (and I suspect also in this case) not be made analytically. You need to either apply some heuristic to classify the points (e.g. by clustering), or try out the $2^{N-1}$ partitions. You might also be able to start with some guessed partition, do the fit and then use the fit to improve the partition.

In any case, for a given partition, for each subset compute the average and subtract it from all points in that subset. Then you can fit a single line through the shifted points (as described in Anton's answer: treat the coordinates as components of complex numbers and use the square roots of the sum of their squares), and then shift it back by the two averages to get the two parallel lines.

P.S.: I just realized you want to minimize the sum of distances and not squared distances. That's rather unusual and more difficult. The principles with respect to partitioning are the same, but you can't use Anton's nice fitting method, since it's derived from the minimization of the sum of squares. In any case, your weights can be included as weights in the sums as usual.

• I don't expect an analytical solution as you point out the partitioning and fitting problems are need to be solved together. Sum of distances may help in suppressing the outliers but sum of distance squares is also ok. – xonobo Sep 19 '15 at 10:28
• @xonobo: I see. I think if you do sum of distances and not squared distances, you'd need to subtract the median instead of the average, but the median point may be different along different directions, so this might introduce further need for iterative correction, where you could subtract the median along some direction, then fit the lines, and then check whether the median along the direction of the fitted lines is the same; else iterate. (Again, you could take your weights into account in forming the median.) – joriki Sep 19 '15 at 10:34