Let's have a set of $N$ points at positions $\vec{R}_i$, where $i=1...N$. They are displaced into arbitrary positions $\vec{r}_{M(i)}$, where $M(i)=1...N$. The problem is to find a map $M: i \mapsto M(i)$ such that $S = \sum_{i=1}^N |\vec{r}_{M(i)}-\vec{R}_i|^2$ is a minimum. In other words, we want to renumber the points in the second set such that sum of squares between corresponding points is a minimum. Any idea where to look for a solution of this problem?
Asked
Active
Viewed 170 times
0
-
Where do these points live? $\mathbb R^n$ for some $n$? – TonyK Sep 23 '14 at 11:35
-
I have $\mathbb{R}^3$. It looks like this is related to the following question: link – Roman Sep 23 '14 at 11:44
-
So you're looking for an algorithm to solve that problem?? – Henry Sep 23 '14 at 11:54
-
At least I would like to know in which direction to look. Some toy problem to understand how to solve these problems without doing a brute force permutation. This probably goes under the name "matching problem". – Roman Sep 23 '14 at 11:59
-
I think finding a minimum matching in a full bipartite graph is the solution here. Edit: Roman was faster. Edit 2: Turns out he wasn't. Make two sets of nodes, compute the distance between the nodes, produce the bipartite graph with weights are the distances, and compute a minimum matching. – sebigu Sep 23 '14 at 11:59
-
Thanks sebigu. This helps a lot. Looking into that now. – Roman Sep 23 '14 at 12:04
-
I just found that this is the Munkres' Assignment problem (Hungarian algorithm) explained nicely here: link – Roman Sep 23 '14 at 12:48