# given a set of points in cartesian plane find the point which has shortest sum of distance from all points

This I have reduced to Given a set of n points find out a point X,Y such that the $\sum_{i=1,n} (x_{i}-X)^2 + (y_{i}-Y)^2$ is minimum. Now as per the comments I found out that this is wrong. Can someone tell me the right approach please?

-
Yes, it's right. –  joriki Apr 6 '11 at 10:41
The title is wrong, though. This point has the least sum of squared distances from all points. –  joriki Apr 6 '11 at 10:42
@joriki - the title is right. Does that mean my calculation is wrong? –  Manoj R Apr 6 '11 at 10:49
Yes, one of them must be wrong. The sum of distances is $S_1=\sum \sqrt{(x_i-X)^2+(y_i-Y)^2}$; the sum of squared distances is $S_2=\sum \left((x_i-X)^2+(y_i-Y)^2\right)$. Minimizing them gives different results in general. Your result correctly minimizes $S_2$, which is also what you wrote in the text. If you in fact want to minimize $S_1$, which is what you wrote in the title, the result doesn't do that. Usually one minimizes $S_2$; minimizing $S_1$ doesn't give such a nice result. –  joriki Apr 6 '11 at 10:55
Yes, it's a complicated calculation. No, I don't think there's a simple relationship to the other result. If you really need this, it might be best to solve it numerically. Are you sure $S_1$ is really what you want? There are other reasons for minimizing $S_2$, not just simplicity. For instance, that gives you the maximum likelihood estimate if the $(x_i,y_i)$ are measurements with Gaussian error distribution. But of course there are also cases where you need $S_1$, e.g. if you want to minimize the sum of distances to be travelled from a central repository. –  joriki Apr 6 '11 at 11:57

The sum of the distances is not nearly as nice of a function. The point of minimal total distance to $3$ points is called the Fermat point $P$ of the triangle $ABC$, which is either the vertex with angle greater than $\frac{2\pi}{3}$ or the unique point in the interior so that $\angle APB = \angle BPC = \angle CPA = \frac{2\pi}{3}$. The case of $4$ points is actually even easier to solve, since the total-distance minimizing point is either the intersection of the diagonals of a convex quadrilateral, or the interior point if the points are not in convex position. For more information, see the geometric median or Fermat-Weber point.