title: Find the closest set of points to another set
body: <p>I have two sets, <strong><em>A</em></strong> and <strong><em>B</em></strong>, with <em>N</em> and <em>M</em> points in <em>R^n</em> respectively. I know that <em>N</em> &lt; <em>M</em> always.</p>
  
  <p>The distance between two points, <strong>P</strong> and <strong>Q</strong>, is denoted by <em>d(</em> <strong>P</strong>,<strong>Q</strong> <em>)</em>. As the problem is generic, this distance could be any function (e.g. Euclidean distance).</p>
  
  <p>I want to find the closest subset of <strong><em>B</em></strong> to <strong><em>A</em></strong>. Mathematically I would say, I want to find the subset <strong><em>C</em></strong> of <strong><em>B</em></strong> with size <em>N</em> with the minimal global distance to <strong><em>A</em></strong>. The global distance between <strong><em>A</em></strong> and <strong><em>C</em></strong> is given by</p>
  
  <pre><code>D(A,C) = min([sum(d(P_i,Q_i),i=1,N) with P_i in A and Q_i in C* for C* in Permutations of C]) 
  </code></pre>
  
  <p>I've been thinking about this problem and I did an algorithm that get a local optimum, but not necessarily the optimal:</p>
  
  <p>Step 1) Find the nearest point of each point of <strong><em>A</em></strong> in <strong><em>B</em></strong>. If there are no points repeated, I found the optimal subset and finish the algorithm. However, if there are points repeated, go to step 2.</p>
  
  <p>Step 2) Compare their distances (of course I compare the distance between points with the same closest point). The point with the minimal distance keeps the point previously found and the others change their <em>desired</em> point for the "next" closest point that have not been selected for another point yet.</p>
  
  <p>Step 3) Check if all the points are different. If they are, finish. If not, go back to step 2.</p>
  
  <p>Any idea? Trying all the combinations is not a good one (I should calculate M!/(M-N)! global distances)</p>