6
$\begingroup$

I have an algorithm problem here. It is different from the normal Fermat Point problem or Geometric Median problem.

Given a set of $n$ points in the plane, I need to find which one can minimize the sum of distances to the rest of $n-1$ points.

Ideally I'd like to have an algorithm for any distance; but giving a nice solution for the usual Euclidean distance is also fine.

Is there any algorithm you know of run less than $O(n^2)$?

Thank you.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

Since you have to compare a sum of square roots, it is not clear/unknown if this problem is in NP. Otherwise, if you assume you can compute sum of square roots and compare them, then I am unaware of an algorithm that works in faster than quadratic time. For approximation, you can just approximate the 1-median using known algorithms in linear time, and then just take the closest point to this center. This would give you a constant approximation. A better approximation can be had by working somewhat harder.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Is it just as hard to minimize the sum of the l1 or l_infty distances? $\endgroup$
    – jbapple
    Jan 15, 2012 at 16:52
  • 3
    $\begingroup$ The $L_\infty$ and $L_1$ do not involve square roots, so these metrics are easier. If you are willing to minimize the sume of square distance then the problem is also easy (I think one can argue that the closest point to the centroid is the optimal solution). In particulr, for $L_1$, you can solve the problem in each dimension separately, so $O(n \log n)$ should not be hard. Since, in the plane, $L_\infty$ is just $L_1$ rotated by 45 degrees, the same trick should work for $L_\infty$. $\endgroup$
    – Sariel Har-Peled
    Jan 15, 2012 at 23:39
  • $\begingroup$ +1 and thank you. Could you also comment on the Manhantan distance on discrete grid points in the plane? Also what about minimize sum of distances on complete graphs? $\endgroup$
    – littleEinstein
    Jan 16, 2012 at 17:23
  • $\begingroup$ @littleEinstein: Manhattan distance is the $L_1$ distance I was asking about: en.wikipedia.org/wiki/Norm_%28mathematics%29#p-norm $\endgroup$
    – jbapple
    Jan 17, 2012 at 4:39
0
$\begingroup$

The computation can be improved by space partition tree for all convex distance functions including $L_2$. By using the mean of the points in each leaf, one can compute a lower bound for the sum of distances in $O(|I|)$ with $|I|$ the total number of leafs. This lower bound is based on the following simple inequality: \begin{equation} \sum_{x\in\Omega} d(x,y)\geq \sum_{i\in I} |\Omega_i| d(\bar{x}_i,y), \end{equation} where $\Omega$ is the point set, $\{\Omega_i\}_{i \in I}$ are the leafs of space partition, and $\bar{x}_i$ is the mean of the points in each leaf.

This inequality allows quickly removing points which cannot be the minimizer. The way of doing so is to pick a candidate point $x^*$ from $\Omega$ and compute the sum of distance $s^*=\sum_{x\in\Omega} d(x,x^*)$. Do space partition and compute the lower bound of sum of distances for the rest of the points. If a lower bound is greater than $s^*$, then we know the corresponding point cannot be the minimizer.

One can grow the tree adaptively and use this result to remove the points much as possible during different stages of comparison.

Improve this answer
$\endgroup$

Your Answer

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

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