2
$\begingroup$

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?

  • 1
    Some terminology which may help you investigate existing work is "geometric median" aka "Fermat-Weber point". Wikipedia has [an article](http://en.wikipedia.org/wiki/Geometric_median) which discusses the L-2 case.2011-08-21
  • 0
    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.2011-08-21
  • 0
    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.2011-08-21

2 Answers 2