Блог пользователя ZeyadKhattab

Minimum Angle Between 2 vectors from a given set of vectors (3D)
Автор ZeyadKhattab, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

sort by polar angle?

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Google is your friend!

→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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)

→ Ответить