data structure for movable points in 3d

Question

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?

Answer 1

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.