4
$\begingroup$

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?

  • 0
    Yes, it's right.2011-04-06
  • 1
    The title is wrong, though. This point has the least sum of *squared* distances from all points.2011-04-06
  • 0
    @joriki - the title is right. Does that mean my calculation is wrong?2011-04-06
  • 0
    @Manoj: Then you need to take the square root of each term in your sum.2011-04-06
  • 4
    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.2011-04-06
  • 0
    @jokiri :- Thanks for the reply. So how can I now go about finding the point which has shortest sum of distance. It seems to complicated calculation. Can I find it out using $S_{2}$ somehow.2011-04-06
  • 1
    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.2011-04-06

1 Answers 1

6

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.