ZeyadKhattab's blog

Minimum Angle Between 2 vectors from a given set of vectors (3D)
By ZeyadKhattab, history, 5 years ago, In English

Can anyone explain the solution for this problem 102014F - Directional Resemblance ?

The problem basically says:

We are given N vectors in 3D and we want to find 2 vectors such that the angle between them is minimum.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

sort by polar angle?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://neerc.ifmo.ru/trains/zurich/analysis/20170426.pdf

Google is your friend!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

I solved that problem with a KD tree. Normalize the vectors, the distance will be proportional to the angle between them so you can use a KD tree to answer closest point.

Or you can use the same thing normalizing vectors in the sphere of same radius and solve it with the general idea for closest pairs (the idea in the editorial)

→ Reply