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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Metric space is the wrong notion. The definition does not even guarantee that distances are computable. $\endgroup$– Felipe VolochCommented Aug 18, 2010 at 23:33
-
$\begingroup$ The assumption is that the distance can be computed in constant time. $\endgroup$– Dan BrumleveCommented Aug 18, 2010 at 23:46
-
1$\begingroup$ Basically you are given a distance table but you only have enough time to examine slightly more than a square root of its entries. $\endgroup$– Dan BrumleveCommented Aug 18, 2010 at 23:53
-
$\begingroup$ are you willing to tolerate approximate answers ? that will open up the range of possibilities. $\endgroup$– Suresh VenkatCommented Aug 20, 2010 at 2:54
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
6
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.
answered Aug 18, 2010 at 23:50
-
$\begingroup$ Thanks, this is a helpful reference. It looks like my suspicion was completely wrong! $\endgroup$ Commented Aug 19, 2010 at 0:14
-
$\begingroup$ 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. $\endgroup$ Commented Aug 19, 2010 at 0:25
-
$\begingroup$ @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. $\endgroup$ Commented Aug 19, 2010 at 0:55
-
$\begingroup$ @Joseph: The bound given by Bentley on p. 227 is $O(n\log^{d-1}n)$. Did I miss something? $\endgroup$ Commented Aug 19, 2010 at 13:02
-
1$\begingroup$ The link to
sciencedirect.comis broken, but the article can be found at doi:10.1006/jagm.1997.0873 (Zbl 0888.68061). $\endgroup$ Commented May 13, 2023 at 15:58
$\begingroup$
$\endgroup$
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.
answered Aug 19, 2010 at 16:31
$\begingroup$
$\endgroup$
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).
answered Aug 20, 2010 at 3:29