3
$\begingroup$

Given $n$ points in 2D, e.g., $p_1,p_2,....,p_n$, there are $n^2$ possible pairs of points. I want to output the list of $n^2$ pairs, but sorted according to their distance (e.g., the pair of two points that are closest is the first pair in the output, and so on).

Is there an algorithm to do this with running time better than $O(n^2 \log n)$? If there was no metric property and the "distance" of each pair of points was unrelated to all other distances, the lower bound would be $\Omega(n^2 \log n^2)$ based on the lower bound for sorting $n^2$ values, but perhaps we can use the properties of the Euclidean distance to do better?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Consider all the point on the x-axis, then you are describing sorting $X-X$. A special case of $X+Y$ sorting(one can actually show they are equivalent in terms of running time). This is not known to be sortable in less than $O(n^2 log n)$ time. Interestingly $O(n^2)$ comparisons suffice.

$\endgroup$

Your Answer

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

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