6
$\begingroup$

I stumbled on this problem and I wanna know if there is a better solution. There are $n$ 3d vectors with $x$, $y$, and $z$ components and I wanna find all pairs of perpendicular vectors in this set. Is there any better way than to verify all possible pairs of 3 vectors, some kind of optimization (not the obvious ones)?

$\endgroup$
  • 2
    $\begingroup$ You want to know the better solution, what is your solution? What are obvious optimizations? $\endgroup$ – Evil Sep 10 at 14:29
  • 1
    $\begingroup$ I think this is his solution "to verify all possible pairs" @Evil $\endgroup$ – narek Bojikian Sep 10 at 17:18
5
$\begingroup$

The problem can be solved in time $\tilde{O}(n^{4/3})$, using several algorithms:

There is an essentially matching lower bound due to Erickson, New lower bounds for Hopcroft's problem. See also Williams and Yu, Finding orthogonal vectors in discrete structures.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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