3
$\begingroup$

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.

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

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – avocado
    Commented Feb 3, 2013 at 6:28
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Feb 3, 2013 at 6:45
  • $\begingroup$ 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). $\endgroup$
    – Raphael
    Commented Feb 3, 2013 at 9:48
  • $\begingroup$ @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. $\endgroup$
    – avocado
    Commented Feb 3, 2013 at 11:57
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Feb 3, 2013 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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