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

Related videos on Youtube

anonymoose
Author by

anonymoose

Updated on October 30, 2020

Comments

  • anonymoose
    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 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
      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
      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.
    • anonymoose
      anonymoose about 12 years
      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
    anonymoose about 12 years
    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?
  • Peter Taylor
    Peter Taylor about 12 years
    Aren't you assuming the L-2 norm?