4

I have many points (+100,000) in 3 dimensional space. I need to use nearest neighbor and range queries. Firstly I used kdtree (k=3) but each point has a velocity attribute. Their location is not static, they change their location. The problem begins here. It is easy to do nearest neighbor and range queries with their old locations. But I have to calculate their new locations according to the their velocity. I have to find nearest neighbor and search in range after calculate their new location.

Everytime the points change their locations I must update kdtree but it is costly. It slows me down. Do you have any suggestion or is there any better data structure for this situation?

Taha Altuntaş
  • 93
  • 1
  • 1
  • 4

1 Answers1

2

An octree or octkey can be faster. An octkey usually uses a Morton curve or a hilbert curve. It reduces the dimension and fills the space. It's often uses in map application. To find the orientation in 3d a gray code can help to find the correct quadrant. Here is an interesting thread about moving objects: http://xboxforums.create.msdn.com/forums/p/59841/368276.aspx. It recommend a quadtree, linked list or ternary trees.

Micromega
  • 12,486
  • 7
  • 35
  • 72
  • I have heard about octree but never heard Morton curve or hilbert curve. How do they solve this velocity problem? I will appreciate if you explain more detailed. – Taha Altuntaş Aug 28 '13 at 10:40
  • I have wrote a php class hilbert curve @ phpclasses.org. you can also google for bing maps quadkey for an explanation. But it could also make sense to use a range query only for static objects. For other objects use a simple data structure like a linked list. – Micromega Aug 28 '13 at 10:56