<p>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.</p>

CC BY-SA 3.0
2012-01-15T16:52:51.937Z
Is it just as hard to minimize the sum of the l1 or l_infty distances?
jbapple
CC BY-SA 3.0
2012-01-15T23:39:18.883Z
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
CC BY-SA 3.0
2012-01-16T17:23:19.060Z
+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?
littleEinstein
CC BY-SA 3.0
2012-01-17T04:39:53.097Z
@littleEinstein: Manhattan distance is the $L_1$ distance I was asking about: http://en.wikipedia.org/wiki/Norm_%28mathematics%29#p-norm
jbapple
CC BY-SA 3.0
2012-01-15T05:52:10.810Z
2012-01-15T05:52:10.810Z
Sariel Har-Peled
<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2017-01-29T18:47:23.303Z
2017-01-29T18:47:23.303Z
hck
<p>I have an algorithm problem here. It is different from the normal <a href="http://en.wikipedia.org/wiki/Fermat_point" rel="nofollow">Fermat Point problem</a> or <a href="http://en.wikipedia.org/wiki/Geometric_median" rel="nofollow">Geometric Median problem</a>.</p>

<p>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.</p>

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

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

<p>Thank you.</p>

<ds.algorithms>
algorithm to find a point among n points in plane to minimize the sum of distances
littleEinstein
# algorithm to find a point among n points in plane to minimize the sum of distances

(Asked by: username_0 on 2012-01-15)

I have an algorithm problem here. It is different from the normal [Fermat Point problem](http://en.wikipedia.org/wiki/Fermat_point) or [Geometric Median problem](http://en.wikipedia.org/wiki/Geometric_median).

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.

**Tags:** ds.algorithms


---

## 2 answers

### Answer by username_1 on 2012-01-15. Score: 8

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.

> **Comments:**
> **username_2**: Is it just as hard to minimize the sum of the l1 or l_infty distances?  
> **username_1**: 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$.  
> **username_0**: +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?  
> **username_2**: @username_0: Manhattan distance is the $L_1$ distance I was asking about: http://en.wikipedia.org/wiki/Norm_%28mathematics%29#p-norm  

---

### Answer by username_3 on 2017-01-29. Score: 0

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.


---

