minimizing sum of distances
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 3point 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 "1D 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.
Related videos on Youtube
anonymoose
Updated on October 30, 2020Comments

anonymoose about 3 years
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 1D 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 yearsSome terminology which may help you investigate existing work is "geometric median" aka "FermatWeber point". Wikipedia has an article which discusses the L2 case.

Austin Mohr about 12 yearsI'm nitpicking, but mathematicians generally use "conjecture" for a possible but unproven solution to a problem. "Hypothesis" is generally refers to the "if" part of an "ifthen" statement.

anonymoose about 12 yearsTHanks 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 about 12 yearsGot it, I clarified my post. Would my approach still be valid if I used the x and y axis medians instead of the means?

Peter Taylor about 12 yearsAren't you assuming the L2 norm?