# algorithm to find a point among n points in plane to minimize the sum of distances

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.

• 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$. – Sariel Har-Peled Jan 15 '12 at 23:39
• @littleEinstein: Manhattan distance is the $L_1$ distance I was asking about: en.wikipedia.org/wiki/Norm_%28mathematics%29#p-norm – jbapple Jan 17 '12 at 4:39
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: $$\sum_{x\in\Omega} d(x,y)\geq \sum_{i\in I} |\Omega_i| d(\bar{x}_i,y),$$ 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.