Finding the best algorithm for nearest neighbor search in a 2D plane with moving points

Question

I am looking for an efficient way to perform nearest neighbor searches within a specified radius in a two-dimensional plane. According to Wikipedia, space-partitioning data structures, such as :

• k-d trees,
• r-trees,
• octrees,
• quadtrees,
• cover trees,
• metric trees,
• locality-sensitive hashing,
• and bins,

are often used for organizing points in a multi-dimensional space and can provide O(log n) performance for search and insert operations. However, in my case, the points in the two-dimensional plane are moving at each iteration, so I need to update the tree accordingly. Rebuilding the tree from scratch at each iteration seems easier, but I would like to avoid it if possible because the points only move slightly between iterations.

I have read that k-d trees are not naturally balanced, which could be an issue in my case. R-trees, on the other hand, are better suited for storing rectangles. Bin algorithms, on the other hand, are easy to implement and provide near-linear search performance within local bins.

I am working on an autonomous agent simulation where 1,000,000 agents are rendered in the GPU, and the CPU is responsible for computing the next movement of each agent. Each agent is influenced by other agents within its line of sight, or in other words, other agents within a circular sector of angle θ and radius r.

Given these considerations, what would be the best algorithms for my use case?

Answer 1

I expect that nearly every data structure offers a way to update a particular value stored in the data structure.

For instance, with an quadtree, if the position of a point changes slightly, you can look its prior position in the data structure, check whether the new position lies within the same cell, and if not, traverse up the tree (to the parent, grandparent, etc.) to find the first region that contains the new position, and then traverse downward from there. If the point has moved only a little bit, that may be faster than deleting the old location and inserting the new location, or building a new quadtree from scratch.

I expect that a similar method can be applied to any space-partitioning tree.

I would suggest that you try implementing each of the standard data structures, with this refinement for updating positions that are already in the data structure, and evaluate how well each works on your dataset/workload. That should tell you which works best. If any more specific question arises out of that, you will be in a good position to ask a more focused question here.