# minimizing sum of distances

2,946

## Solution 1

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.

## Solution 2

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:
2,946

Author by

### anonymoose

Updated on October 30, 2020

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?

• Peter Taylor about 12 years
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.
• Austin Mohr about 12 years
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.