Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

Please answer with a concrete proof.

share|improve this question
    
Could you post your approach for non-discrete sets? –  G. Bach Feb 2 '13 at 12:53
5  
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
add comment

migrated from cstheory.stackexchange.com Feb 2 '13 at 21:15

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

1 Answer

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.

share|improve this answer
    
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
    
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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.