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

Given N≥2 point-sites in a Euclidean space, suppose we wish to find the point X (which is not necessarily a site) whose sum of distances to the N sites [call it F(X)], is minimal.

  1. Show that F(X) is a continuous concave-∪ function.
  2. If the sites all lie on a line, then show the optimal X is the median site (in order along the line) if N is odd, or anywhere between the two bi-medians, if N is even. Hence the point X we seek is a multi-dimensional generalization of the concept of "median."
  3. Assume from now on that the sites do not all lie on a line. Show F(X) is strictly concave-∪ and hence has a unique minimum.
  4. Suppose that we start from any point X which is not one of the N sites, and compute (as our new X) the weighted mean of the N sites, where the weight for site k is chosen to be proportional to 1/dist(X, sk) and of course the proportionality constant is chosen so that the weights sum to 1. Prove that this decreases F(X) unless X is already at the optimum location, in which case it leaves X unaltered.
  5. In the preceding question, what goes wrong if the old X is located exactly at a site? How can we avoid this difficulty?

Answers

a. The "distance to a site" function is continuous and concave-∪, and since any sum of concave-∪ functions is concave-∪, we conclude F(X) is. Obviously, F(X)→∞ when |X|→∞. Therefore, F(X) has a global minimum.

b. If there are more sites on one side of X, moving X in that direction will decrease F(X).

c. The only lines on which the "distance to a site" function is not strictly concave-∪ is along lines through the site. So if the sites do not all lie on a line then F(X) will be strictly concave-∪ on every line.

d. Using the preceding puzzle, we see that the new X (call it Q) uniquely minimizes the weighted sum of squared distances to the sites. Let sk denote site k and let wk denote its weight (which is proportional to its reciprocated distance to X). Hence

∑1≤k≤N wk |Q-sk|2 ≤ ∑1≤k≤N wk |X-sk|2

with equality if and only if Q=X. Hence

∑1≤k≤N |Q-sk|2 / |X-sk| ≤ F(X).

Now note the identity

|Q-sk|2 = {(|Q-sk| - |X-sk|) + |X-sk|}2 = (|Q-sk| - |X-sk|)2 + |X-sk|2 + 2(|Q-sk| - |X-sk|)·|X-sk|.

Applying this identity and simplifying the result a bit, we find

2 F(Q) + ∑1≤k≤N (|X-sk| - |Q-sk|)2 / |X-sk| ≤ 2 F(X).

Because any weighted sum of squares (if the weights are positive) is positive (unless it is zero, which occurs only if each and every square is 0) we conclude

F(Q) ≤ F(X)    with equality only if Q=X.

This "descent" result was first published by Endre Weiszfeld (whose name later changed to Andrew Vazsonyi) in 1937.

e. If X lies at a site, the weight of that site would be infinite (division by zero) hence our X-updating formula would be inapplicable. This actually is a symptom of a difficulty with this iteration – it is possible for it to "get stuck" very near a site for an arbitrarily large number of iterations time before it finally departs.

One way to avoid that difficulty is to start the Weiszfeld iteration at someplace better than the best site. The iteration will never be able to land on a site from then onward, due to the descent property. The "best site" means B=sk such that the kth row of the distance matrix has minimum sum. Applying a Weiszfeld iteration starting from B but only considering the N-1 other sites, yields a point W. It is easy to see that the direction from B to W is the steepest descent direction for F(X) at X=B, unless B is already optimum. Hence somewhere on the line segment BW, is a better point than B (if any exists). Indeed a point on this line segment lying arbitrarily close to B will do, unless B already is optimum. Hence a way to find a better-than-B point is to start at W, and repeatedly halve your distance to B (staying on the line segment BW) until the point is found.

The optimum point X is known as the Fermat-Steiner-Torricelli-Weber point (or some subset of these names).


Return to puzzles

Return to main page