# Choose a “middle” point from a set

I read a post which talks about pretty much the same problem. But here I simplify the problem hoping that a concrete proof can be offered.

There is a set $A$ which contains some discrete points (one-dimensional), like $\{1, 3, 37, 59\}$. I want to pick one point from $A$ which minimizes the sum of distances between this point and others.

There may be lot of posts out there, and my problem is just the one-dimensional version of those. I know how to prove it if $A$ is not discrete, but I fail when $A$ is discrete like above.

-

## migrated from cstheory.stackexchange.comFeb 2 '13 at 21:15

This question came from our site for theoretical computer scientists and researchers in related fields.

Could you post your approach for non-discrete sets? – G. Bach Feb 2 '13 at 12:53
Just pick the point closest to the median (your problem is the "geometric distance" problem which reduces to median in 1-d case). – Vor Feb 2 '13 at 13:02
There is a trivial $\Theta(n^2)$-time and -space algorithm. What are your non-functional restrictions? – Raphael Feb 2 '13 at 21:35
@vor The median is in the set. – Yuval Filmus Feb 3 '13 at 3:07

For a point $x$, let $d(x)$ be the sum of distances between $x$ and points in $A$. For $x \notin A$, the derivative $d'(x)$ has the nice formula $$d'(x) = |\{y \in A : y < x\}| - |\{y \in A : y > x\}|.$$ This shows why the median is the best answer when you don't have to select a point from $A$. For a point $x \in A$, $d(x)$ is the same as your objective function, hence the solution is to choose the median. You can find the median in linear time, as described in Wikipedia and various other resources.
If A is a contiguous set, I know why the point is the median. But here A is a discrete set, I don't quite understand your proof. – loganecolss Feb 3 '13 at 6:28
In short, if $x$ is any point to the left of the median, then $d'(x) < 0$, and so it is always better to slightly increase $x$. If $x$ is any point to the right of the median, then $d'(x) > 0$, and so it is always better to slightly decrease $x$. So the median is the unique optimum. – Yuval Filmus Feb 3 '13 at 6:45
For a uniformly spread set, I immediately agree. But when there are clusters of close points, the argument becomes less clear (to me), that is why $d'$ has this form. Also, the set $\{-2,-1,1,2\}$ has no unique median; any value from $[-1,1]$ suffices, with $0$ the canonical choice. Furthermore, the median is not unique when chosen from the set (in the example, both $-1$ and $1$ work). For the question, we can just choose either one of them (if "the" median is indeed the correct solution). – Raphael Feb 3 '13 at 9:48
@Raphael, if A is a uniformly spread set, I also agree that the point should be the median. What I am not sure about is just that when A is not a uniformly spread discrete set. – loganecolss Feb 3 '13 at 11:57