# Is sorting pairwise distances as hard as sorting arbitrary points?

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?

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

• That's very interesting and a little surprising with respect to the comparison model. Thank you.
– user15587
Jun 29, 2019 at 18:34
• 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.
– user15587
Jun 29, 2019 at 20:45
• 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?
– user15587
Jul 3, 2019 at 17:28
• 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)}. Jul 4, 2019 at 17:45
• Thanks. That's very interesting indeed.
– user15587
Jul 4, 2019 at 18:44