Algorithm to maximize dot product between two sets of vectors

I have two sets of vectors $(\mathbf{l}_i)_{1\le i \le n}$ and $(\mathbf{r}_i)_{1 \le i \le n}$. Each vector $\mathbf{l}_i$ is in $[0,1]^4$, same for $\mathbf{r}_j$. I'd like to maximize the dot product $\mathbf{l}_i \cdot \mathbf{r}_j$, i.e. find tuples $(i,j)$ s.t. $\mathbf{l}_i \cdot \mathbf{r}_j$ is as big as possible.

To be clear, if $\mathbf{l}_i=(\mathbf{l}_{i,1},\mathbf{l}_{i,2},\mathbf{l}_{i,3},\mathbf{l}_{i,4})$ and $\mathbf{r}_{j}=(\mathbf{r}_{j,1},\mathbf{r}_{j,2},\mathbf{r}_{j,3},\mathbf{r}_{j,4})$, then:

$$\mathbf{l}_i \cdot \mathbf{r}_j=\sum_{k=1}^4 \mathbf{l}_{i,k} \mathbf{r}_{j,k}$$

-
The number of tuples I'd like to find should be ideally a parameter of the algorithm, i.e. find the $K$ tuples $(i,j)$ that lead to the greatest values of $\mathbf{l}_i \cdot \mathbf{r}_j$. I won't mention $K$ in the complexities below, let's say $K \ll n$.

-
I'm looking for $O(n \log^k n)$ ideas. The naive algorithm takes $\Theta(n^2)$ time, which is too big for me ($n \approx 2^{20}$).

-
My first idea was to try to solve the problem in dimension 2, with the additional constraint on the input $|\mathbf{r}_j|=1$. In that case it is easy to design a $O(n \log n)$ algorithm: sort all $\mathbf{r}_j$ according to their angle with $(1,0)$, then for all $i$, find $\mathbf{l}_i$ in that list by binary search.

In my opinion, intermediary tasks might be:

• Try to generalize the formula $\mathbf{u} \cdot \mathbf{v}=|\mathbf{u}| |\mathbf{v}| \cos(\mathbf{u},\mathbf{v})$ to dimension $4$.

• Try to remove the condition $|\mathbf{r}_j|=1$ from the algorithm in dimension $2$.

I have no idea on how to solve these two problems.

I'm asking this in a single question because I'm also interested in more general algorithms that may give approximations (e.g. that solve the "maximum dot product" problem in arbitrary dimension).

As a completely different approach, assuming that $d < \log n$, one can generate $O(\log n)$ random vectors $w_i$ with unit norm. For each $w_i$ we look at $\langle l_i, w_i \rangle$ and $\langle r_i, w_i \rangle$. Take the top largest $O(\sqrt n)$ from each list, as potential candidates. After completing we have $O(\sqrt n \log n)$ candidates, and then we check the dot products between the pairs. It is important that $d < \log n$ so that $O(\log n)$ vectors are sufficient to cover the unit sphere well. In your case where $d = 4$ it would seem to be that $d << \log n$.

StackExchange Computer Science Q#76736, answer score: 5