How do I find a point that is closest to multiple points on a 2D cartesian plane? So let's say I have n number of points that has coordinates (x1, y1), (x2, y2), (x3, y3), ... (xn, yn). Now I want to find a point that has a shortest distance to all these points. Let the point I want to find be P(x,y)
So now the total distance is:
$$
D=\sum_{i=1}^{n}(\sqrt{(x_i-x)^2+(y_i-y)^2})
$$
And to find the optimal point of D:
$$
D^{'}=\sum_{i=1}^{n}(1/2 (x_i^2-2xx_i+x^2+y_i^2-2yy_i+y^2 )^{-1/2} (-2x_i+2x-2y_i+2y))=0
$$
But I cant seem to be able to find a solution to this equation. So is there a way to solve this problem?
 A: This is exactly the problem of computing the Geometric Median of $n$ points.
Unfortunately, there is no explicit elementary formula for calculating the geometric mean in the general case.
There are some iterative approximate algorithms though that will work just fine. One simple method is the Weiszfeld's algorithm but there are probably more sophisticated methods.
A: The problem is not so easy if you start with $D$ since you need an estimate to sart with.
To get it, in a preliminary step, consider instead
$$F(x,y)=\sum_{i=1}^{n}\left({(x_i-x)^2+(y_i-y)^2}\right)$$ which gives as estimates
$$x_*=\frac 1n \sum_{i=1}^{n}x_i \qquad \text{and} \qquad y_*
=\frac 1n \sum_{i=1}^{n}y_i$$
Now, back to the orginal problem, let
$$D(x,y)=\sum_{i=1}^{n}d_i\qquad \text{with}\qquad d_i=\sqrt{(x_i-x)^2+(y_i-y)^2}$$
$$\frac{\partial D(x,y)}{\partial x}=\sum_{i=1}^{n}\frac {x-x_i}{d_i}=0\qquad \text{and}\qquad \frac{\partial D(x,y)}{\partial y}=\sum_{i=1}^{n}\frac {y-x_i}{d_i}=0$$ So, you have two nonlinear equations for two variables and this is simple to solve using Newton-Raphson method.
Let us take the following case
$$\left(
\begin{array}{cc}
x_i & y_i \\
 9 & 7 \\
 5 & 1 \\
 6 & 2 \\
 4 & 4 \\
 5 & 4
\end{array}
\right)$$
We have $x_*=5.8$ and $y_*=3.6$. Starting with these estimates, Newton-Raphson method converges to $x=5.08$ and $y=3.70$ using two iterations.
