Find a distance between point clouds efficiently

Question

I have 2 point clouds (a set of points in 3D space) and an iterative algorithm. One of the clouds (let's call it A) is constant on each iteration and another (call it B(i)) is slightly different on each iteration (it means that B(i+1) differs from B(i) only in a few points). On every iteration i for each point from A my algorithm should find closest point from B(i).

My question is: how can I compute these distances in a fastest way possible?

Here is what I've already tried:

• Brute force computing (compute all distances for each pair of points from A and B(i)) - absolutely inefficient.
• On each iteration build a KD-tree for B(i) and then find closest points for each point from A - faster then brute force, but still computationally expensive (because I should rebuild KD-tree on each iteration).

It seems like I should utilize a fact that B(i) and B(i+1) differs only slightly from each other, but I still can't come up with a good solution. Thank you in advance.

Answer 1

For each point in A, keep a record of which point was closest in the previous iteration B(i).

At iteration i+1, make a list of each point in B that was deleted or changed between i and i+1, and also each new point in B.

For each point in A:

• If the previous closest point in B was not changed or removed, then you only need to compute the distance from A to the closest of the new points in B(i+1) and check against the previous closest in B(i).
• If the previous closest point in B(i) was changed or removed, then you need to compute the closest distance from A to any of the points in B(i+1)

You can use a KD-tree or whatever spatial data structure you like to speed this up, but the optimization comes from the first case. Note that a KD-tree allows removal so you don't need to rebuild the whole thing from scratch each iteration.