# 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.

• 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. – avocado 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. – avocado Feb 3 '13 at 11:57
• You're both right that the median is defined only for sets of odd size, while for sets of even size it's really an interval. – Yuval Filmus Feb 3 '13 at 17:01