7
$\begingroup$

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?

$\endgroup$
  • $\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
1
$\begingroup$

This is only a partial answer.

I think it is not complex to show that if question 1 can be done in $o(n^2 \log n)$, then so can be question 2. So according to the comment by Willard Zhan in the OP's question, your first question should be open as well.

A reduction could be as follows:

Assume your input to question 2 is $\{x_i\}_{1 \leq i \leq n}$. Then construct an input for question 1 as follows:

$\{T + x_i\}_{1 \leq i \leq n} \cup \{- x_i\}_{1 \leq i \leq n}$ for a sufficiently large constant T.

Then the answer to question 1 with these $2n$ points could be easily translated to an answer to question 2, as pairs of the form $(T + x_i, -x_j)$ in the answer to question 1 are easily differentiated from the rest, and correspond directly to the answer of question 2, taking into account that:

  • $|(T + x_i) - (- x_j) | = |T + x_i + x_j | = T + x_i + x_j > T / 2$

  • $|(T + x_i) - (T + x_j) | = |x_i - x_j | < T / 2$

  • $|-x_i - (-x_j) | = |- x_i + x_j | < T / 2$

| cite | improve this answer | |
$\endgroup$

Your Answer

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

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