Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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