6
$\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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ That's very interesting and a little surprising with respect to the comparison model. Thank you. $\endgroup$
    – user15587
    Jun 29, 2019 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$
    – user15587
    Jun 29, 2019 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$
    – user15587
    Jul 3, 2019 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, 2019 at 17:45
  • $\begingroup$ Thanks. That's very interesting indeed. $\endgroup$
    – user15587
    Jul 4, 2019 at 18:44

Your Answer

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