<p>I don't know if you are interested in those kind of results, but Brassard, Dupuis, Gambs and Tapp devised a quantum algorithm that does just that. It finds an element $X_i$ such that $|\mathsf{middle}(X_i)-\mathsf{middle}(X_{min})|&lt; O(\epsilon)$ (when all distances are normalized to be in $[0, 1]$). and requires $O(\frac 1\epsilon \sqrt N\log N)$ calls to the distance function (which you call metric) where $X_{min}$ is the middle you are looking for.</p>

<p>What might surely interest you is that in the first paragraph of the section on the median algorithm, they provide an argument that in the worst case, with a general metric, $\Omega(N^2)$ calls to the distance function is required without a quantum computer. Here is their argument :</p>

<blockquote>
  <p>[..] consider the case in which all the points are at the same
  distance from each other, except for two points that are closer than the rest of the points.
  These two points are the medians of this ensemble. In this case, classically we would
  need to query the oracle for the distances between each and every pair of points before
  we can identify one of the two medians. (We expect to discover this special pair after
  querying about half the pairs on the average but we cannot know that there isn’t some
  other even closer pair until all the pairs have been queried.) This results in a lower
  bound of $\Omega(N^2)$ calls to the oracle.</p>
</blockquote>

<p>This give a lower bound on the number of calls to the oracle (distance function) which itself lower-bounds the time complexity.</p>

<p>Here is a <a href="http://arxiv.org/pdf/1106.4267v1" rel="nofollow">link</a> to the article.</p>

CC BY-SA 3.0
2012-01-12T14:51:13.817Z
2012-01-12T18:24:26.433Z
2012-01-12T18:24:26.433Z
lamontap
<p>There's a rather large literature on this problem. In brief, the problem you're looking at is called the $1$-median problem for a metric space. Since you're allowing for things "near" the middle, I'll assume approximations are ok. I also don't know what you mean by space less than $n^2$, since the input size itself is $n^2$. </p>

<p>Having said that, for an arbitrary metric space you can get a "sublinear" approximation (i.e one that runs in $o(n^2)$ time. Specifically, <a href="http://people.csail.mit.edu/indyk/metrics99.ps">Piotr Indyk showed</a> that you can get a $(1+\epsilon)$ approximation in time linear in $n$ and polynomial in $1/\epsilon$. </p>

<p>For structured spaces you can also do quite well. In Euclidean space, <a href="http://dl.acm.org/citation.cfm?id=1007400">core-set techniques for the $k$-median problem</a> (of which the 1-median is a special case) give you similar bounds (linear in n) to get arbitrarily good approximations. The caveat in this case is that the solution you get might not be one of the input points. </p>

CC BY-SA 3.0
2012-01-11T13:42:09.993Z
As for the space, we usually mean the working space. But I agree with you that a clarification of denis should be beneficial.
Yoshio Okamoto
CC BY-SA 3.0
2012-01-11T08:30:59.510Z
2012-01-11T08:30:59.510Z
Suresh Venkat
<p>Given $N$ points $X_i$ in a metric space
and a measure of "middleness"
$ \qquad \qquad \mathsf{middle}( X_i ) \equiv
\frac{1}{N} \sum_j \mathsf{metric}( X_i, X_j ) $<br>
can one find an $X_i$ near the middle of all $N$ points,
i.e. roughly minimizing $\mathsf{middle}( X_i )$,<br>
in time and space both better than $O( N^2 )$ ?<br>
If not in general, are there cases that can be done &mdash; trees, Euclidean metrics ?  </p>

<p>Clarification: by "space better than $O(N^2)$" I mean,
are there approximate methods that give many nearby pairs 
after looking at $O(N^{1+\epsilon})$ of all pairs ?<br>
This is broader than just middles.
Of course, guarantees are then gone, or empirical or statistical.
But methods that work for $N$ 10000 or 1000000 
would have broad application.<br>
(Is that clear, is it worth a separate question ?)</p>

<ds.algorithms>
Fast approximate middle of points in a metric space?
Denis
# Fast approximate middle of points in a metric space?

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

Given $N$ points $X\_i$ in a metric space
and a measure of "middleness"
$ \qquad \qquad \mathsf{middle}( X\_i ) \equiv
\frac{1}{N} \sum\_j \mathsf{metric}( X\_i, X\_j ) $  
can one find an $X\_i$ near the middle of all $N$ points,
i.e. roughly minimizing $\mathsf{middle}( X\_i )$,  
in time and space both better than $O( N^2 )$ ?  
If not in general, are there cases that can be done — trees, Euclidean metrics ?

Clarification: by "space better than $O(N^2)$" I mean,
are there approximate methods that give many nearby pairs
after looking at $O(N^{1+\epsilon})$ of all pairs ?  
This is broader than just middles.
Of course, guarantees are then gone, or empirical or statistical.
But methods that work for $N$ 10000 or 1000000
would have broad application.  
(Is that clear, is it worth a separate question ?)

**Tags:** ds.algorithms


---

## 2 answers

### Answer by username_2 on 2012-01-11. Score: 12 | Accepted answer

There's a rather large literature on this problem. In brief, the problem you're looking at is called the $1$-median problem for a metric space. Since you're allowing for things "near" the middle, I'll assume approximations are ok. I also don't know what you mean by space less than $n^2$, since the input size itself is $n^2$.

Having said that, for an arbitrary metric space you can get a "sublinear" approximation (i.e one that runs in $o(n^2)$ time. Specifically, [Piotr Indyk showed](http://people.csail.mit.edu/indyk/metrics99.ps) that you can get a $(1+\epsilon)$ approximation in time linear in $n$ and polynomial in $1/\epsilon$.

For structured spaces you can also do quite well. In Euclidean space, [core-set techniques for the $k$-median problem](http://dl.acm.org/citation.cfm?id=1007400) (of which the 1-median is a special case) give you similar bounds (linear in n) to get arbitrarily good approximations. The caveat in this case is that the solution you get might not be one of the input points.

> **Comments:**
> **username_3**: As for the space, we usually mean the working space. But I agree with you that a clarification of denis should be beneficial.  

---

### Answer by username_1 on 2012-01-12. Score: 4

I don't know if you are interested in those kind of results, but Brassard, Dupuis, Gambs and Tapp devised a quantum algorithm that does just that. It finds an element $X\_i$ such that $|\mathsf{middle}(X\_i)-\mathsf{middle}(X\_{min})|< O(\epsilon)$ (when all distances are normalized to be in $[0, 1]$). and requires $O(\frac 1\epsilon \sqrt N\log N)$ calls to the distance function (which you call metric) where $X\_{min}$ is the middle you are looking for.

What might surely interest you is that in the first paragraph of the section on the median algorithm, they provide an argument that in the worst case, with a general metric, $\Omega(N^2)$ calls to the distance function is required without a quantum computer. Here is their argument :

> [..] consider the case in which all the points are at the same
> distance from each other, except for two points that are closer than the rest of the points.
> These two points are the medians of this ensemble. In this case, classically we would
> need to query the oracle for the distances between each and every pair of points before
> we can identify one of the two medians. (We expect to discover this special pair after
> querying about half the pairs on the average but we cannot know that there isn’t some
> other even closer pair until all the pairs have been queried.) This results in a lower
> bound of $\Omega(N^2)$ calls to the oracle.

This give a lower bound on the number of calls to the oracle (distance function) which itself lower-bounds the time complexity.

Here is a [link](http://arxiv.org/pdf/1106.4267v1) to the article.


---

