We have two sets of vectors of positive numbers, $X$ and $Y$ where for $x\in X$ we write $x=(x_1,x_2,\ldots,x_k)$ and similarly for $y\in Y$ we write $y=(y_1,y_2,\ldots,y_k$).

We are given two vectors $l=(l_1,l_2,\ldots,l_k)$, and $u=(u_1,u_2,\ldots,u_k)$ such that $l_i\le u_i$ for all $i$.

We want to find all pairs $(x,y)$, $x\in X$, and $y\in Y$ such that $l_i\le x_i+y_i\le u_i$

Handwaving a bit, we can do this in a divide and conquer sort of way, separating each set into pieces that are larger and smaller than $l_i/2$ and throwing away the pairs where both are in the smaller half. This gives a recurrence $$T(m,n) = T(m,n/2) + T(m/2, n/2) + c(m+n)$$ where $m=|X|$ and $n=|Y|$. For equal size sets, this gives $T(n,n) = O(n^{1.7}), which is better than quadratic, but less than I would hope for.

A similar question could be asked for three or more sets.

We have two sets of vectors of positive numbers, $X$ and $Y$ where for $x\in X$ we write $x=(x_1,x_2,\ldots,x_k)$ and similarly for $y\in Y$ we write $y=(y_1,y_2,\ldots,y_k$).

We are given two vectors $l=(l_1,l_2,\ldots,l_k)$, and $u=(u_1,u_2,\ldots,u_k)$ such that $l_i\le u_i$ for all $i$.

We want to find all pairs $(x,y)$, $x\in X$, and $y\in Y$ such that $l_i\le x_i+y_i\le u_i$

Handwaving a bit, we can do this in a divide and conquer sort of way, separating each set into pieces that are larger and smaller than $l_i/2$ and throwing away the pairs where both are in the smaller half. This gives a recurrence $$T(m,n) = T(m,n/2) + T(m/2, n/2) + c(m+n)$$ where $m=|X|$ and $n=|Y|$. For equal size sets, this gives $T(n,n) = O(n^{1.7})$, which is better than quadratic, but less than I would hope for.

A similar question could be asked for three or more sets.