Puzzle #??: The point with least sum of squared distances

Given N point-sites in a Euclidean space, suppose we wish to find the point X (which is not necessarily a site) whose sum of squared distances to the N sites is minimal.

  1. Show that X is the mean of the N sites.
  2. More generally if we wish to minimize the weighted sum of the squared distances to the N sites where each site k is associated with a pre-specified positive weight wk, then show that X is the weighted mean (using the same weights) of the N sites.

Answers

a. The squared distance function x2+y2+...+z2 obviously is strictly concave-∪ hence the sum of squared distances to the sites – call it G(X) – is strictly concave-∪ (and goes to ∞ when |X|→∞) hence has a unique minimum. This minimum occurs when the partial derivatives of G(X) with respect to each of its coordinates, all are 0.

G(X) = ∑1≤k≤N (X-sk)2

Hence G(X)'s partial derivative with respect to (say) the y-coordinate of the vector X is

2 ∑1≤k≤N (y - tk)

where tk denotes the y-coordinate of sk. Setting this to 0 we find

y = N-1 ∑1≤k≤N tk

which is the arithmetic mean of the tk. The discussion is the same for every other coordinate. We conclude X must be the coordinatewise arithmetic mean of the sites.

b. If the weights are positive integers then the same proof goes through after simply making wk copies of site k. If they are positive rationals this is still valid by scaling by common denominator. If they are positive reals it still is valid by continuity and the fact the rationals are everywhere dense within the reals. (Or, you could just redo the approach of the preceding proof but introducing weights into all expressions; that also works.)


Return to puzzles

Return to main page