What is the most general class of metric spaces for which the closest pair of points in any finite subset can be found in time O(n^(1+eps))? I have studied how to do this in O(n log(n)) in the plane, and I believe I can generalize the same method to some other surfaces, but it does not work in 3-space (maybe it is possible but I suspect not). Are there any interesting examples of metric spaces in which this problem can be solved efficiently?



What is the most general class of metric spaces for which the closest pair of points in a finite subset can be found in time O(n^(1+eps))?
I assume you are aware of the classic paper by Jon Bentley,
"[Multidimensional divide-and-conquer](http://portal.acm.org/citation.cfm?id=358850)"
[*Commun. ACM* **23**(4):214-229 (1980)],
in which he showed how to find the closest pair of points in $\mathbb{R}^3$
in the Euclidean metric in $O(n \log n)$ time.
His algorithm works in arbitrary dimensions in $O(n \log^{d-1} n)$.
I realize I am not answering your question about metric spaces, but it might be worth revisiting
his algorithm to see how heavily it leans on the norm. 


Rabin's 1976 randomized algorithm achieves $O(n)$ expected time.
An updated detailed analysis is in the paper
"[A Reliable Randomized Algorithm for the Closest-Pair Problem](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WH3-45NJK2G-2&_user=10&_coverDate=10%252F31%252F1997&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1434955821&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=fe7a5e8a4209763de823c9438fb642f0)"
by Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen
[*Journal of Algorithms* **25**(1): 19-51 (1997)].
Again I am not addressing your focus on other metric spaces, but these efficient algorithms
for Euclidean distance would be a place to start.


