3
$\begingroup$

Given two sets $A$ and $B$, both of $n$ points $p \in \mathbb{R}^3$. I want to find a bijective function $f:A \rightarrow B$ so that the cost $C$ is minimal. It's defined as the sum of all pair's euclidean distances.

$$C =\sum_{p \in A}{|p - f(p)|}$$

Can this be calculated directly? If not, what is the most efficient way to find it? Please provide the formula or algorithm.

$\endgroup$
5
$\begingroup$

Such a thing is called a minimum weight perfect matching for a bipartite graph. There is a polynomial time $O(n^3)$ algorithm for this with an interesting history stretching back to Jacobi, often called the Hungarian method. Some lecture notes give background in Section 1.2.

$\endgroup$
5
$\begingroup$

This is called a "transportation problem", which is a special case of a network flow problem. Efficient algorithms are well-known. The linear programming formulation uses variables $x_{ij} \in [0,1]$ for $i \in A$, $j \in B$.

minimize $\sum_{i,j} |i-j| x_{ij}$ subject to $\sum_i x_{ij} =1$, $\sum_j x_{ij} = 1$, $0 \le x_{ij} \le 1$.

$\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.