Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Yes, it's right. –  joriki Apr 6 '11 at 10:41
1  
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
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. –  joriki Apr 6 '11 at 10:55
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. –  joriki Apr 6 '11 at 11:57

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.