# Pair points between to sets minimizing the global distance

I have two set of points in the plane or space, which could be for instance radar contacts over two successive scans. I'd like to pair them so that the sum of squared distances is minimal.

One difficult case, if for instance there is a serie of aligned and equidistant points in the first set, can be found in the second one shifted by one interval (they all moved together). The sum of squared distances does promote the desired solution, but if for every point we look for the closest match in the second set, we go in the wrong way.

I somewhat suspect that the problem can't be solved for the absolute minimum without checking all possible sets of pairs. But maybe there is a heuristic for finding a local minimum that would be the absolute one in most cases?

• It's unclear what the "series of aligned and equidistant points" means. Can you please clarify? May 13 at 18:13
• @HEKTO [4,5,6,7] moving to [5,6,7,8]. May 13 at 18:19
• @KellyBundy - it's still confusing... We're talking about points in 2D or 3D, right? May 13 at 18:24
• @HEKTO I just didn't bother to write it multidimensional. May 13 at 18:25
• I'm having a hard time understanding what your question is and what you want. Are you looking for an algorithm to pair them in a way that minimizes the sum of squared distances? Based on the second paragraph of your question, it sounds like you are not. Are you looking for some other objective function (other than sum of squared differences) that has better properties or better meets your needs? If so, exactly what are your needs? What are the criteria you will use for judging a proposed objective function?
– D.W.
May 13 at 19:53