# Find a point that minimizes the sum of distances to n lines (not square distances!).

We have n lines, each one of them is represented by a point $$p_i$$ which is the projection of the origin on the line and a unit vector $$v_i$$ which is the direction of the line.

Finding the point that minimizes the sum of squared distances is pretty easy, we can just use the fact that the point that minimizes the sum of squared distances to n points (the center of mass) is the average of them (easy to prove using partial derivatives), from that we can infer that if we project the optimal point x on all of the lines it must be the average of those points (otherwise there would have been a point that minimizes the sum more than x), and then we can use simple linear algebra to create a formula for x:

$$x = \left(\sum_{i = 1}^{n}{(I - v_iv_i^t)}\right)^{-1} \sum_{i = 1}^{n}{p_i}$$

And like explained in this answer: Sum of rejection matrices is invertible the matrix above is invertible iff not all the lines are parallel, and if they are parallel we can just take the intersection of the lines with any plane that is diagonal to the lines and take the center of mass / average of those points.

But what if we want to minimize the sum of distances instead of squared distances? And is there any linear or polynomial time algorithm that would bring us a constant approximation for the sum if not an optimal one?

HINT:

Say you have $$f_1$$, $$\ldots$$, $$f_m$$ affine functions on $$\mathbb{R}^n$$ and you want to minimize $$\sum_{i=1}^m |f_i(x)|$$ This is equivalent to the linear programming problem:

minimize $$\sum_{i=1}^m t_i$$ in $$(t_1, \ldots, t_m, x)$$, where $$t_i \ge f_i(x)$$, $$t_i \ge - f_i(x)$$, $$i=1,\ldots, m$$.

Obs: For general convex optimization problems, see for instance the courses by Prof. Stephen Boyd.

$$\bf{Added:}$$

The solution above only covers the case of lines in the plane.

Say now we have the problem

minimize $$\sum ||A_i x + b_i||_2$$

where $$x \mapsto A_i x + b_i$$ are affine functions from $$\mathbb{R}^n$$ to $$\mathbb{R}^{n_i}$$, $$i=1, \ldots, m$$.

This is reduced to the second order cone programming

minimize $$\sum_{i=1}^m t_i$$

where $$||A_i x + b_i || \le t_i$$, $$i=1, \ldots, m$$.

• $f_i$ is not an affine function because it returns a vector not a number (the vector from the point x to line $i$), if you want to define $f_i$ as the size of the vector instead then it's also not affine because it has square root. Unless there is a different way to define $f_i$ that I don't see? Apr 5, 2020 at 17:25
• @Tomer Wolberg: You are totally right, thank you! The answer only covered the planar case. For the general case, we can use second order cone programming, I added some details. Apr 5, 2020 at 23:02
• I looked at it again and I'm not sure how this is reduced to SOCP. Doesn't SOCP minimizes $f^t x$? What is $f^t$ here? May 13, 2020 at 18:56
• @Tomer Wolberg: The variables are $(x, t_1, \ldots, t_m)$. There are constraints on the variables. And the $f$ should be $(0, 1, \ldots, 1)$ ( so in the objective function only the $t_i$'s appear). So the so called $x$ is in fact $(x,t)$. You could call that bold $x$. The name is not that important. May 13, 2020 at 23:49
• I think there might be a problem with this solution. If we have 5 points (not lines) in 2D space and we want to find the point that minimizes the distance to those points, we can just create 5 3D lines that pass through those points and are perpendicular to the 2D plane, then if we find the point that minimizes the sum of distances to the lines (with your algorithm) and project it back to the 2D plane we get the point that minimizes the sum of distances to the points, however there's a proof that there is no analytic solution for this problem. But I can't find any mistake in your solution. May 20, 2020 at 14:07