1
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ It's unclear what the "series of aligned and equidistant points" means. Can you please clarify? $\endgroup$
    – HEKTO
    May 13 at 18:13
  • $\begingroup$ @HEKTO [4,5,6,7] moving to [5,6,7,8]. $\endgroup$
    – Kelly Bundy
    May 13 at 18:19
  • $\begingroup$ @KellyBundy - it's still confusing... We're talking about points in 2D or 3D, right? $\endgroup$
    – HEKTO
    May 13 at 18:24
  • $\begingroup$ @HEKTO I just didn't bother to write it multidimensional. $\endgroup$
    – Kelly Bundy
    May 13 at 18:25
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    May 13 at 19:53

1 Answer 1

Reset to default
1
$\begingroup$

If you're looking for an algorithm to pair the points in a way that minimizes the sum of squared distances, this is an instance of the bipartite matching problem (or assignment problem). You have an edge between each point from the first set and each point from the second set, whose length is equal to the square distance between those two points. There are standard algorithms for solving the bipartite matching/assignment problem, which you could apply here.

These algorithms do not take advantage of the geometric structure here, so it is possible there might be even more efficient algorithms possible.

I recommend also learning about https://en.wikipedia.org/wiki/Correspondence_problem and https://en.wikipedia.org/wiki/Point-set_registration.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.