Detecting approximate sum collisions in two lists.

Suppose two equal-length lists of double precision numbers $A=(A_1, \ldots, A_N)$ and $B=(B_1, \ldots, B_N)$. Given a constant, $\epsilon > 0$, I want an efficient algorithm for finding 4-tuples of the form $(A_a, A_b, B_c, B_d)$ for which $|A_a + A_b - (B_c + B_d)| < \epsilon$.

One thing you could do is form the sum sets $S_A:=\{A_j + A_k\}$ and similarly, $S_B$, sort them, and then iterative over these in parallel looking for elements that satisfy the requirement.

This algorithm should have complexity of the form $O(N^2)$ (with perhaps a constant multiplicative factor). Forming the sum sets has complexity $\sim O(N^2)$, the sorting has complexity $\sim N \log N$; the final step is a single pass through both sum sets; also complexity $O(N^2)$.

Is there an algorithm that does better than $O(N^2)$?

I believe there is no known algorithm with running time faster than $O(N^2)$, even if you work with integers and ask for a tuple such that $A_a + A_b - (B_c + B_d) = 0$ (i.e., is exactly zero).

There are algorithms with running time $O(N^2)$ and space $O(N)$. Basically, they iterate through the sum sets $S_A$ and $S_B$ in order, without ever storing the entire sets in memory, by using a priority queue.

There are also algorithms that with running time $O(N^{4/3})$, if the numbers are chosen uniformly at random over some range and if you can choose $N$ appropriately (i.e., if the relationship between $N$ and the size of that range can be chosen appropriately) and if you only care about finding one such 4-tuple (even though many might exist). I suspect this probably isn't of use to you.

StackExchange Computer Science Q#68444, answer score: 2