3
$\begingroup$

Let $f$ map a point in the plane to the sum of the distances to each element in a given set of points. Can $f$ have multiple local minima?

For example, there is only one relative minimum when the given set is the set of vertices of an equilateral triangle, since if you're at some point in the plane other than the center of the triangle, you can always get a lower sum of distances by moving closer to the center (I think).

1 Answers 1

4

Except for some special cases, the answer in general, is no, there aren't multiple local minima.

This result appeared as an article in the American Mathematical Monthly. You can see the whole article here: http://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/nellipse.pdf

The locus of points at a given 'sum of distances' from a set of $n$ given points is called an $n$-ellipse, and in general, the $n$-ellipse is a closed curve with convex interior. I believe this was also proved in the article above.

  • 1
    Since the question asks whether $f$ **can** have a local minimum, it would be worthwhile to elaborate on the special cases where multiple local minima exist. These are precisely when $n$ is even and the $n$ points are collinear; the local minima form the line segment joining the middle two points. This is the same reason why you need an additional condition to uniquely define the median of an even number of scalars.2012-02-14