Find orthogonal (integer) vectors in set

Question

I have very large sets $A,B$ of 4-tuples of integers, and I would like to find $(x_1,y_1,z_1,w_1)\in A,(x_2,y_2,z_2,w_2)\in B$ such that $$x_1x_2 + y_1y_2 + z_1z_2 + w_1w_2 = 0.$$

Of course the naive $|A||B|$-time algorithm is too slow for me. Is there a better algorithm?

In 2D you can normalize all the vectors then for any $a\in A$, there are only two possible unit vectors orthogonal to $a$ so it can be done in something like $|A|\log|B|$ time.

But in 4D, for any vector $a\in A$, there is a whole 3D subspace of vectors orthogonal to $a$, and I don't see an easy way of quickly (i.e. faster than linear time) determining which vectors in $B$ lie in that subspace.

Answer 1

Thank you to @InuyashaYagami for pointing out that paper in the comment above. It cites "Cutting Hyperplanes for Divide-and-Conquer" (Chazelle, 1993) which gives an $O(n^{2d/(d+1)}(\log n)^{1/(d+1)})$ algorithm for determining intersections between $n$ hyperplanes and $n$ points in $d$-space (note: this is equivalent to determining whether there are vectors $a\in A,b\in B$ for $A,B\subset \mathbb R^{d+1}$ such that $a_1b_1+\cdots+a_{d+1}b_{d+1} = 0$, since we can rearrange to get $a_1(b_1/b_{d+1}) +\cdots + a_d(b_d/b_{d+1}) = -a_{d+1}$). In my case ($d = 3$) this is $O(n^{3/2}(\log n)^{1/4})$ which is quite close to the lower bound of $\Omega(n^{4/3})$ established in "New Lower Bounds for Hopcroft's Problem" (Erickson, 1995).

Unfortunately the algorithm given by Chazelle seems quite complicated to say the least. Here is a simpler, $O(n^{5/3})$ (average-case) algorithm I came up with for the integer version of this problem, which might perhaps be faster in practice (I will have to try implementing Chazelle's algorithm to be sure...):

First, find a prime $p$ close to $\sqrt[3]{cn}$ for some choice of constant $c$ which can be adjusted to improve performance.

Now we know that for any solution $x\in A,y\in B$, we will have $$x_1y_1 + x_2 y_2 + x_3y_3 + x_4 y_4 \equiv 0~~~\text{(mod $p$})$$ So then $$y_1 + Py_2 + Qy_3 + Ry_4 \equiv 0~~~\text{(*)}$$ where $P=x_2x_1^{-1}$, $Q=x_3x_1^{-1}$, $R=x_4x_1^{-1}$ (the case of $x_1\equiv 0$ will have to be handled separately).

So split $A$ into $p^3$ "buckets" depending on $(P,Q,R)$.

Now for each $(y_1,y_2,y_3,y_4)\in B$, figure out which $P,Q,R$ satisfy (*) and just check those buckets, instead of all of $A$ (the values of $P,Q,R$ can be found, at least for most $y$'s, by going through each $P,Q$ and solving for $R$ — in total $p^2$ buckets will need to be searched).

I would be interested to know whether there are reasonably simple algorithms (including perhaps randomized algorithms) which can do better than this.