title: Algorithm design: Track moving points in 3D space
body: <p>This is a language agnostic question, more algorithm design oriented.</p>
  
  <p>Imagine we have an two arrays of points in 3D space (each looks like <code>[(1, 0, 2), (2, 4, 32), ...]</code>)</p>
  
  <p>The first array represents the first state of the points and the second represents a later state where the points have shifted a small amount (not necessarily each by the same distance). <em>Note:</em> A few points could have been removed and some new ones added in the second state.</p>
  
  <p><strong>Problem:</strong> Given these two arrays, how could one match (to a reasonable degree of accuracy) each shifted point to its original point, while also identifying which points are new and did not exist in the first state?</p>
  
  <hr>
  
  <p><strong>Ideas:</strong> I was thinking that some sort of k-means clustering could be applied, but I'm not sure how it would handle the fact that some points could have been removed/added between the states - so I don't think that approach would work well.</p>
  
  <hr>
  
  <p><strong>Edit:</strong></p>
  
  <p>Points are not necessarily added at any particular place in the array and the order is not necessarily maintained for persisting points between states. The distance the points are shifted between states should be relatively small compared to the distance between unique points - otherwise this problem is basically impossible.</p>