Consider 1 dimensional points $x_1, \dots x_n, x_i \in \mathbb{R}$ where the distance between any two points is defined as $d(x_i, x_j) = \vert x_i - x_j \vert$. The goal is to enumerate all $n^2$ pairs of points in increasing order of distance.

The trivial algorithm takes $O(n^2 \log n)$ time but we can do better if we are allowed to build a data structure in a pre-processing phase. It is easy to see that one can build a data structure that takes $O(n \log n)$ time and $O(n \log n)$ space in the following way - we simply sort all of the input points and store the closest candidate for each point in a heap. Then, with $O(\log n)$ delay, I can get an output element. For the point which was popped from the heap, we can add the next closest point using binary search over the input and inserting into the heap (both operations take $O(\log n)$ time). Although this method is better, it still takes $O(n^2 \log n)$ time in total.

Question 1 - My question is whether there is a known lower bound that total enumeration cannot be done in $o(n^2 \log n)$ time. This was listed as an open problem here. I am looking for references that prove a lower bound or a more recent paper that confirms this is still an open problem.

Question 2 - What happens if I replace distance function to $d(x_i, x_j) = x_i + x_j$? Does this make the problem easier and admit $o(n^2 \log n)$ time algorithm?

  • $\begingroup$ The second problem is essentially the X+Y sorting problem, which I believe is still open. I guess sorting the distances has a reduction from it too. $\endgroup$ – Willard Zhan Sep 12 '18 at 16:43

Your Answer

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

Browse other questions tagged or ask your own question.