<p>This is only a partial answer. </p>

<p>I think it is not complex to show that if question 1 can be done in <span class="math-container">$o(n^2 \log n)$</span>, 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.</p>

<p>A reduction could be as follows: </p>

<p>Assume your input to question 2 is <span class="math-container">$\{x_i\}_{1 \leq i \leq n}$</span>. Then construct an input for question 1 as follows:</p>

<p><span class="math-container">$\{T + x_i\}_{1 \leq i \leq n} \cup \{- x_i\}_{1 \leq i \leq n}$</span> for a sufficiently large constant T.</p>

<p>Then the answer to question 1 with these <span class="math-container">$2n$</span> points could be easily translated to an answer to question 2, as pairs of the form <span class="math-container">$(T + x_i, -x_j)$</span> 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: </p>

<ul>
<li><p><span class="math-container">$|(T + x_i) - (- x_j) | = |T + x_i + x_j | = T + x_i + x_j &gt; T / 2$</span></p></li>
<li><p><span class="math-container">$|(T + x_i) - (T + x_j) | = |x_i - x_j | &lt; T / 2$</span></p></li>
<li><p><span class="math-container">$|-x_i - (-x_j) | = |- x_i + x_j | &lt; T / 2$</span></p></li>
</ul>

CC BY-SA 4.0
2020-02-20T10:43:22.147Z
2020-02-20T10:43:22.147Z
gilcu3
<p>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. </p>

<p>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.</p>

<p>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 <a href="https://www.computer.org/csdl/proceedings/focs/1992/2900/00/0267752.pdf" rel="nofollow noreferrer">here</a>. I am looking for references that prove a lower bound or a more recent paper that confirms this is still an open problem.</p>

<p>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?</p>

CC BY-SA 4.0
2018-09-12T16:43:28.020Z
The second problem is essentially the [X+Y sorting](http://cs.smith.edu/~jorourke/TOPP/P41.html) problem, which I believe is still open. I guess sorting the distances has a reduction from it too.
Wei Zhan
<ds.algorithms><time-complexity><lower-bounds>
Lower bound for enumerating k closest pair of points
karmanaut
# Lower bound for enumerating k closest pair of points

(Asked by: username_0 on 2018-09-06)

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](https://www.computer.org/csdl/proceedings/focs/1992/2900/00/0267752.pdf). 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?

**Tags:** ds.algorithms, time-complexity, lower-bounds

> **Comments:**
> **username_1**: The second problem is essentially the [X+Y sorting](http://cs.smith.edu/~jorourke/TOPP/P41.html) problem, which I believe is still open. I guess sorting the distances has a reduction from it too.  

---

## 1 answers

### Answer by username_2 on 2020-02-20. Score: 1

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$


---

