# Find orthogonal (integer) vectors in set

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.

• If you normalize $x_2$ to 1 (assuming for a moment it isn't 0) then you get the equation $-x_1 = y_1 y_2 + z_1 z_2 + w_1 w_2$, so it seems equivalent to the following problem: given a bunch of planes in 3D space and a bunch of points, find a point which is on a plane Commented Apr 2, 2023 at 21:07
• @CommandMaster hmm yes. And I think if you store the (normalized) points of $B$ in an oct-tree you can figure out which ones intersect a certain plane in something like $O(|B|^{2/3}\log |B|)$ time, which is a bit better but still not great... Commented Apr 2, 2023 at 21:26
• It seems like the paper A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem might contain an answer for you, although I'm not certain if it constructs the LSA efficiently. Commented Apr 3, 2023 at 7:17
• This is a well known problem: theory.stanford.edu/~yuhch123/files/orthog-soda.pdf. Maybe you want to mention this link in your question. Commented Apr 4, 2023 at 21:40

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.