# 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$$.
• 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. – Anush Jun 29 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? – Anush Jul 3 at 17:28