5
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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 $\endgroup$ Apr 2 at 21:07
  • $\begingroup$ @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... $\endgroup$
    – pommicket
    Apr 2 at 21:26
  • $\begingroup$ 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. $\endgroup$ Apr 3 at 7:17
  • 1
    $\begingroup$ This is a well known problem: theory.stanford.edu/~yuhch123/files/orthog-soda.pdf. Maybe you want to mention this link in your question. $\endgroup$ Apr 4 at 21:40

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.