2
$\begingroup$

We aim to optimize the execution of a specific task.

Consider a set, P, containing N 2D points. A new query point, p1, is introduced, and the objective is to identify the nearest point in P to p1. If the distance surpasses a specified threshold, p1 is incorporated into P, increasing its cardinality to N+1; otherwise, p1 is disregarded. Subsequently, another query point, p2, undergoes the same process of either addition to P or elimination based on proximity criteria.

This continual influx of points, unbeknownst in advance, necessitates dynamic adjustments to P. It's essential to emphasize that this process is inherently sequential. Our inquiry revolves around identifying efficient data structures for implementing this sequential task. While k-D trees were explored, a notable challenge was discovered: upon adding a point to P, the entire tree must be reconstructed. In simpler terms, the insertion operation of k-D trees appears non-incremental. We are thus seeking alternative data structures that offer efficiency in executing the described task.

$\endgroup$
3
  • $\begingroup$ There are several sampling based robot motion planning algorithms, such as PRM or RRT (see e.g. these slides ). Can you clarify which of these standard approaches you are using, or describe the planning algorithm more precisely? Also, does an update in the environment only need to affect future collision checking, or do existing sampled paths need to be updated to correspond to the new environment as well? $\endgroup$
    – Discrete lizard
    Commented Dec 14, 2023 at 11:01
  • $\begingroup$ @D.W. I have rephrased the whole question body to focus on what exactly I needed and removed the extra information. $\endgroup$ Commented Dec 15, 2023 at 7:47
  • $\begingroup$ Thank you, this is very clear! $\endgroup$
    – D.W.
    Commented Dec 15, 2023 at 19:45

1 Answer 1

3
$\begingroup$

You are looking for a data structure for nearest neighbor search that supports dynamic updates. I suggest reviewing Wikipedia, as it has a good overview of many different data structures.

Inserting an element into a k-d tree does not require rebuilding the entire tree. See https://en.wikipedia.org/wiki/K-d_tree#Adding_elements. In particular, you can insert into the tree efficiently without rebuilding it, and then periodically rebuild the tree, to amortize the cost of rebuilding over many inserts.

Another option is to use locality sensitive hashing. This supports efficient insert and delete operations. It also allows for approximate nearest-neighbor computation, but is not guaranteed to find the exact nearest neighbor. You'll have to decide whether that is sufficient for your application.

$\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.