Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am creating stimuli for an experiment. The stimuli consists of 2 distinct sets of 9 points in a 2D plane. Each set of points can be described by 9 pairs of coordinates. (i.e. http://learnmem.cshlp.org/content/5/6/420/F1.expansion)

I would like to estimate the minimum distance between 2 sets (or patterns) of points. (In the example linked above, I would want to estimate the distance between the "prototype" pattern and the "low" pattern.)

So far I have calculated the Pythagorean distance between every point in pattern A and every point in pattern B, for a total of 81 distance measurements. I believe I now need to match up each point in A to exactly one point in B (trying to minimize the total distance between all pairs). After that step, I would then sum the distances between the matched points. However, I do not know how to do this process.I believe there are over 300,000 possible ways to pair up the dots and I do not know how to calculate all of these possibilities in order to select the best one.

It is not critical that I know the exact distance for any two sets, but I need a reliable estimate. I will need to estimate this distance for many pairs of sets, so I would like to find a solution that is possible to perform for many items within a programming tool, such as R or Matlab.

share|improve this question
1  
Have you considered whether your similarity measure should be invariant under isometries? If I understand correctly, you're asking people to judge the similarity of these patterns and the values of the coordinates don't have any meaning up to at least translations, possibly also rotations -- your measure should reflect this; otherwise you'd be introducing artificial dissimilarity that doesn't correspond to any dissimiliarity a person would perceive. –  joriki Apr 6 '11 at 4:23
    
On a side note, two similar questions have been asked at stackoverflow, stackoverflow.com/questions/3920839/… and stackoverflow.com/questions/5004449/…, without being answered. (That probably doesn't mean there aren't any good answers, just that questions often go unanswered on stackoverflow.) –  joriki Apr 6 '11 at 4:25

1 Answer 1

From a purely combinatorial perspective, you can consider the two sets of points as forming a weighted bipartite graph: let each point in the first set be connected to each point in the other, by an edge whose weight is the distance between the two points. Then what you are looking for is the maximum weighted perfect matching in this graph with all edge weights negated. This is also known as the assignment problem, and polynomial-time algorithms are available.

There might be a more efficient algorithm that exploits the geometric nature of your particular problem, but this is the extent of my knowledge. On the other hand, since your problem size is fairly small (18 vertices, 81 edges), this may be good enough.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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