title: Find a distance between point clouds efficiently
body: <p>I have 2 point clouds (a set of points in 3D space) and an iterative algorithm. One of the clouds (let's call it <em>A</em>) is constant on each iteration and another (call it <em>B(i)</em>) is slightly different on each iteration (it means that <em>B(i+1)</em> differs from <em>B(i)</em> only in a few points). On every iteration <em>i</em> for each point from <em>A</em> my algorithm should find closest point from <em>B(i)</em>.</p>
  
  <p>My question is: how can I compute these distances in a fastest way possible?</p>
  
  <p>Here is what I've already tried:</p>
  
  <ul>
  <li>Brute force computing (compute all distances for each pair of points from <em>A</em> and <em>B(i)</em>) - absolutely inefficient.</li>
  <li>On each iteration build a KD-tree for <em>B(i)</em> and then find closest points for each point from <em>A</em> - faster then brute force, but still computationally expensive (because I should rebuild KD-tree on each iteration).</li>
  </ul>
  
  <p>It seems like I should utilize a fact that <em>B(i)</em> and <em>B(i+1)</em> differs only slightly from each other, but I still can't come up with a good solution. Thank you in advance.</p>