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?
given a set of points in cartesian plane find the point which has shortest sum of distance from all points
-
1Yes, 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. – 2011-04-06
1 Answers
The square of the distance from a point is a quadratic polynomial, so the sum of the squares is quadratic, and the center of the resulting circular paraboloid is the center of mass of the points.
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.