Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have $N$ points in $D$ dimensions, were $D$ is big, for sure more than $100$. $N$ is also big.

The goal is to produce an algorithm in my code, that will take as input this dataset and will give another one (in a different matrix), that will be randomly rotated.

I have used Euler rotation, but the time complexity of it is $O(N\cdot D\cdot D)$.

Chanop and Hartley note in their paper "Optimised KD-trees for fast image descriptor matching", that:

enter image description here

but searching the internet didn't help me much, so I literally don't know how to perform this task. I am not asking for code, but for guidance, for what I should do to achieve my goal.

A relevant -maybe- question is this in this site.

share|cite|improve this question
What's the question? Do you know how to multiply a Householder matrix and a vector in $O(d)$ time? That I can do. The second part I cannot do, because I don't know what a tree is. – Stephen Montgomery-Smith Jul 3 '14 at 2:16
Also, how do you use Euler rotations if $D \ne 3$? – Stephen Montgomery-Smith Jul 3 '14 at 2:19
Multiplying by householder matrices does reflection not rotation. You could try Givens rotations. – daw Jul 3 '14 at 8:21
I used the generalizations described in the link. Yes that was the case, but after daw's comment, everything got cleared up, tnx! – gsamaras Jul 3 '14 at 12:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.