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.

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).

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
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. –  Rahul Feb 14 '12 at 3:03
add comment

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.