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?
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.