# 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))?

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?

-
Metric space is the wrong notion. The definition does not even guarantee that distances are computable. –  Felipe Voloch Aug 18 '10 at 23:33
The assumption is that the distance can be computed in constant time. –  Dan Brumleve Aug 18 '10 at 23:46
Basically you are given a distance table but you only have enough time to examine slightly more than a square root of its entries. –  Dan Brumleve Aug 18 '10 at 23:53
are you willing to tolerate approximate answers ? that will open up the range of possibilities. –  Suresh Venkat Aug 20 '10 at 2:54

I assume you are aware of the classic paper by Jon Bentley, "Multidimensional divide-and-conquer" [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" 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.

-
Thanks, this is a helpful reference. It looks like my suspicion was completely wrong! –  Dan Brumleve Aug 19 '10 at 0:14
Beautiful. One thing I do not understand: essentially, Dan's question is reduced to a different one. Namely, is it possible to find an $\mathbb{R}^d$ such that there are n points at the same mutual distances as the points in the original metric space? and how large is d, and does it depend on n? or am I wrong. –  Piero D'Ancona Aug 19 '10 at 0:25
@Piero: $n$ points in any metric space embed isometrically into $\ell_\infty^{n-1}$. If the points are labeled $x_0,\dots, x_{n-1}$, map a point $x$ to $(d(x,x_0),\dots,d(x,x_{n-1}$. You of course cannot embed every finite metric space isometrically into a Hilbert space. –  Bill Johnson Aug 19 '10 at 0:55
@Joseph: The bound given by Bentley on p. 227 is $O(n\log^{d-1}n)$. Did I miss something? –  François G. Dorais Aug 19 '10 at 13:02
@François: You are right, I only meant the algorithm still works, but I implied the complexity was the same when it is not. Corrected now. Thanks for catching this! –  Joseph O'Rourke Aug 19 '10 at 20:46

A popular assumption in theoretical computer science for algorithms of this type is that the metric have bounded "doubling dimension". The doubling dimension of a metric space is the smallest number k such that, for every r and every ball B of radius 2r, there is a cover of B by at most 2^k balls of radius r. Normed real vector spaces of finite dimension have bounded doubling dimension, for instance.

For randomized near-linear closest pair algorithms with this assumption, see e.g. Hildrun, Kubiatowicz, Ma, and Rao, "A note on the nearest neighbor in growth-restricted metrics", SODA 2004.

-
Another approach you can take is as follows. Since the closest pair can be solved by $n$ invocations of a nearest neighbor query, you could examine the set of techniques available for performing near-neighbor queries in $n^\epsilon$ time.