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?