5
$\begingroup$

If we have $n$ points in $\mathbb{R^d}$, what is the complexity of sorting the $O(n^2)$ pairwise distances?

Clearly the complexity is $\Omega(n^2)$ but is there a reduction to show it is as hard as sorting $n^2$ arbitrarily chosen numbers?

As a concrete sub question, is the complexity $\Theta(n^2\log{n})$ in the comparison model?

$\endgroup$
6
$\begingroup$

This is an open question even for one-dimensional point sets. In this setting, the distance-sorting problem is equivalent to sorting X+Y, where $X$ is the input set and $Y=-X$.

$\endgroup$
  • $\begingroup$ That's very interesting and a little surprising with respect to the comparison model. Thank you. $\endgroup$ – Anush Jun 29 at 18:34
  • 2
    $\begingroup$ cs.smith.edu/~jorourke/TOPP/P41.html is actually very informative. In particular, that the problem can be solved with $O(n^2)$ comparisons. However it currently takes $O(n^2 \log n)$ time to work out which comparisons those should be. $\endgroup$ – Anush Jun 29 at 20:45
  • $\begingroup$ What is the status of this question for points in 2d? Is it know that the problem can be solved in $O(n^2)$ comparisons as in the 1d case? $\endgroup$ – Anush Jul 3 at 17:28
  • $\begingroup$ I think it can. Fredman proved that any set of N items from a set of Γ permutations can be sorted using O(N + log Γ) comparisons (by a nonuniform family of decision trees). In this case, N is the number of distances and Γ is the number of possible distance permutations. Γ is also the number of full-dimensional cells in an arrangement of N constant-degree algebraic surfaces in R^2n. It shouldn't be too hard to prove that Γ= N^{O(n)} = 2^{O(n log n)}. $\endgroup$ – Jeffε Jul 4 at 17:45
  • $\begingroup$ Thanks. That's very interesting indeed. $\endgroup$ – Anush Jul 4 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.