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.
Best Answer
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.