How to find a point on a line that minimizes sum of distances from three given points?

Question

This is a cross-post of a question on MathOverflow where it didn't get much attention: https://mathoverflow.net/questions/337892/how-to-find-a-point-on-a-line-that-minimizes-sum-of-distances-from-three-given-p

Let there be given three points $x_1$,$x_2$,$x_3$ and a line $l$ on a plane. Does there exist an explicit method of finding such a point $p$ on $l$, that sum of distances of $p$ from $x_1$,$x_2$,$x_3$ is possibly minimal? Such result for two given points and a line is trivial and known as the Heron's theorem commonly used in optics to find a path of a ray of light.

All I know about the solution is that if $p$ minimizes the sum of distances, then $$\cos{\alpha}+\cos{\beta}+\cos{\gamma}=0$$

The equation above comes directly from the derivative of the function of sum of distances if we assume that the line has equation $y = 0$:

$$\frac{d}{dx} \sum_{i=1}^3 \sqrt{(x-x_i)^2+(0 - y_i)^2} = 0$$ $$\sum_{i=1}^3 \frac{x-x_i}{\sqrt{(x-x_i)^2+(y_i)^2}} = 0$$ $$\cos{\alpha}+\cos{\beta}+\cos{\gamma}=0$$

However, that is not really helpful neither for construction nor finding the solution analytically. Some rare situations may be solved using Brianchon's theorem.

That is, if we add symmetrical reflections of $x_1$,$x_2$,$x_3$ on the opposite sides of $l$ and the six points are vertices of a hexagon circumscribing a conic section, then the intersection of the main diagonals minimizes the sum of distances. However it is far from general solution.

Answer 1

There is no analytic solution in the present situation about standard special functions.

As already mentioned, the equation to solve for $x$ is : $$\sum_{i=1}^3 \frac{x-x_i}{\sqrt{(x-x_i)^2+(y_i)^2}} = 0$$ This equation can be transformed into a polynomial equation of degree higher than 5.

It is known that the general polynomial equations of degree up to 4 can be analytically solved in terms of a finite number of elementary functions.

The general polynomial equation of degree 5 cannot be analytically solved in terms of a finite number of elementary functions. It requires some special functions of Jacobi theta kind : http://mathworld.wolfram.com/QuinticEquation.html

In the case of the present problem, as far as I know there is no standard special function available to solve the related polynomial equation of high degree.

Thus don't expect an analytical solution with a finite number of standard functions.

In practice numerical calculus is easy. For example with data ( points in black) : $$(x_1=0\:,\:y_1=6.4)\:;\:(x_2=6\:,\:y_2=10)\:;\:(x_3=14.5\:,\:y_3=7.2)$$

The point noted $x$ drawn in black isn't the optimum. It is a screen copy from the figure publish by NikoWielopolski in his question (of course after rotation making horizontal the given straight line).

In order to obtain a rough approximate solution one can draw the function $f(x)=\sum_{i=1}^3 \frac{x-x_i}{\sqrt{(x-x_i)^2+(y_i)^2}}$ .

The zero of the function is graphically evaluated. $$x\simeq 6.4$$

They are a lot of numerical methods and softwares to solve more accurately the equation.

For example one can find a result as accurate as wanted thanks to the Newton-Raphson method : http://mathworld.wolfram.com/NewtonsMethod.html $$x_m\simeq 6.4017$$

Result drawn in red on the above figure.

Answer 2

You could always do it with non-linear programming. Let $(x_i,y_i)$ be the coordinates of your three points, $(x_p,y_p)$ be the coordinates of $p$, and suppose the line $l$ has equation $y=ax+b$. You can solve the following problem :

$$ min \quad d_{p1}+d_{p2}+d_{p3} $$ subject to \begin{align*} d_{pi} &= \sqrt{(x_p-x_i)^2 + (y_p-y_i)^2} \quad \forall i \in \{1,2,3\}\\ y_p &= ax_p + b \\ x_p,y_p &\in \mathbb{R} \end{align*}

Answer 3

As JJacquelin answered, Newton method is the simplest way to solve your problem.

As usual, you need a guess. You can get it minimizing first the sum of the squared distances that is to say $$\frac{d}{dx} \sum_{i=1}^3 \big({(x-x_i)^2+(0 - y_i)^2}\big) = 0\implies x=\frac 13\sum_{i=1}^3 x_i$$ For the test case, this gives $x_0=6.83$.

Now, for the real problem, Newton method will generate the following iterates $$\left( \begin{array}{cc} n & x_{(n)} \\ 0 & 6.8333333 \\ 1 & 6.3992290 \\ 2 & 6.4017089 \\ 3 & 6.4017090 \end{array} \right)$$

Edit

Making the problem more general for $n$ points, the iterates of Newton method are given by

$$x_{(n+1)}=x_{(n)}-\frac{\sum _{i=1}^n \frac{x_{(n)}-x_i}{\left(x_{(n)}^2-2 x_{(n)} x_i+x_i^2+y_i^2\right)^{1/2}}}{\sum _{i=1}^n \frac{y_i^2}{\left(x_{(n)}^2-2 x_{(n)} x_i+x_i^2+y_i^2\right)^{3/2}}}\qquad \text{with} \qquad x_{(0)}=\frac 1n\sum_{i=1}^n x_i$$ which should converge in a couple of iterations.