Take the 2-minute tour ×

I've been working on a problem recently, and I was hoping you all could help me out. The issue is basically this:

Consider a set of $n$ points $x_1$, $x_2 \ldots x_n$ in a plane $P$. You want to find a point $x_i$ such that the sum of distances between $x_i$ and every other point is minimized. Assume distance is defined as Chebychev distance. In addition, all points have integer coordinates, so a point like $(1.5, 2.4)$ is not valid.

For example, consider the three coordinates below:

$(-100, -100)$, $(0,0)$, $(100,100)$

Now obviously, the point that minimizes the sum of distances is $(0,0)$, because then the total distance is 200, whereas if you picked any of the other two points, then the distance is $200 + 100 = 300$.

After reviewing the replies given, I see that the median minimizes the sum of the distances in a 1-D line. So my conjecture is this: If we compute the median for the x and y axes, call them $x_{med}$ and $y_{med}$, then the point $(x_i , y_i)$ that minimizes the sum of distances is the point closest to $(x_{med}, y_{med})$.

How would I go about devising an algorithm that solves my problem?

share|improve this question
Some terminology which may help you investigate existing work is "geometric median" aka "Fermat-Weber point". Wikipedia has an article which discusses the L-2 case. –  Peter Taylor Aug 21 '11 at 20:50
I'm nit-picking, but mathematicians generally use "conjecture" for a possible but unproven solution to a problem. "Hypothesis" is generally refers to the "if" part of an "if-then" statement. –  Austin Mohr Aug 21 '11 at 21:06
THanks for the links, and information. I updated the OP based on the answers. I read over the article, but I'm still not sure how I would compute that. The suggestions given seem to be specific to Euclidean distance, but I'm using Chebychev distance. –  anonymoose Aug 21 '11 at 21:24
add comment

2 Answers

You are wrong assuming that the point which minimizes the distance is the mean of the points. Take for example the plane case of a triangle. It is well known that the Fermat point minimizes the sum of distances to the three points, and from the definition you can see that the Fermat point is not the centroid, which is the mean of the three points.

If in the 3-point case the assumption you made is not true, it is obviously that in the general case we cannot make this assumption.

share|improve this answer
Aren't you assuming the L-2 norm? –  Peter Taylor Aug 22 '11 at 6:03
add comment

On a "1-D line", the point that minimizes the sum of the distances is the median, not the mean. The mean minimizes the sum of squares of the distances.

share|improve this answer
Got it, I clarified my post. Would my approach still be valid if I used the x and y axis medians instead of the means? –  anonymoose Aug 21 '11 at 21:25
add comment

Your Answer


