I'm reading a recent paper "Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem" by Gregory Valiant on finding approximate closest pairs in $R^d$. Valiant says the current upper bound for this problem is $O(n^2)$.

On Wikipedia however it is said that the 2d divide-and-conquer algorithm can be generalized to solving the problem in $O(n\text{log}n)$ for any number of dimensions. There are no direct sources to this, but in the talk page, a few papers are referenced.

Reading those papers, they all seem to refer to Jon Louis Bentley's thesis from 1980 "Multidimensional Divide-and-Conquer". However as far as I can understand, the closest pair problem is hear described as solved in $O(n\text{log}^dn)$ time.

Hence, I feel like I must have absolutely confused myself on the definitions. Can anyone help me figure out what the correct upper bound for this problem really is?

Update: I should of course define the problem properly: Given a set $S$ of $n$ points from $R^d$, find two points $p, q\in S$, $p\neq q$ which minimise $d(p, q)$, where $d$ is euclidean distance. The model is RAM or similar.

  • 2
    $\begingroup$ To avoid any further confusion, you should carefully define the problem. What exactly is the problem you are talking about? $\endgroup$
    – Juho
    Nov 10, 2014 at 15:58
  • $\begingroup$ You are right. Is the added description sufficient? $\endgroup$ Nov 10, 2014 at 19:41
  • $\begingroup$ Sure is! Is this the problem Valiant considers too? What's the exact quote from the paper? $\endgroup$
    – Juho
    Nov 10, 2014 at 20:11
  • $\begingroup$ He says the current best possible is $O(n^2)$. However thinking about it more closely, $nlog^dn$ us actually $n(logn)^{(logn)}$ worst case, after standard space reduction. And that's much worse than $n^2$. So we actually don't have a way to solve this efficiently for large dimensions. Now I just need to understand if Wikipedia really means it can be done in $nlogn$ for arbitrary dimensions.. $\endgroup$ Nov 10, 2014 at 23:28
  • $\begingroup$ Can you link to the specific page on Wikipedia that makes this claim? (ideally, to the specific section on that Wikipedia page?) Odds are that you have misunderstood Wikipedia (e.g., it is talking about a different problem or a special case), or that Wikipedia is just wrong -- it happens. $\endgroup$
    – D.W.
    Nov 11, 2014 at 0:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.