0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I doubt we can tell you which will be "best", as you haven't given any criteria for evaluating answers that we can use. The algorithm that is fastest might depend on your workload, and since that isn't available in the question, I doubt that this is answerable. We expect you to do a significant amount of work before asking. I would suggest that you try implementing these algorithms, evaluate how well they work on your data, and then see if some more specific question arises. $\endgroup$
    – D.W.
    Dec 21, 2022 at 23:30
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/156356/755, stackoverflow.com/q/74881515/781723. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Dec 23, 2022 at 20:16

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.