# 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.

In this regard, Ken Clarkson's survey of nearest neighbor methods in metric spaces is quite helpful. Among the things he does is review various properties of metric spaces and how they influence the running time of NN algorithms (the doubling dimension mentioned by David is one example considered here).

-