Match unpaired points between two sets

Question

I have two sets, let's call them C and T, of unpaired points, which could for example represent two types of cells. Hence, both points are drawn from the same underlying distribution, but the points in T underwent an additional process/function.

Although biologically debatable, I want to find the most similar points in the T set for each point in the C set. It does not need to be a 1:1 mapping, 1:n is also possible, because the sample sizes might be different.

How can I find such a mapping? Do you know any algorithms (or have other ideas) to achieve this? First, I thought it makes sense to span a graph in both sets by drawing edges between points which are below a certain distance. The distance for each set has to be such that the number of vertices with n edges are approximately the same in both sets. Afterwards I could match all points with k neighbors in set C, with all points with k neighbors in set T. Although I have not implemented this yet, I am unsure how efficient this will be.

Answer 1

This is called the Assignment Problem, or equivalently Weighted Bipartite Matching.

You need a way to compute a numeric distance or cost between any point in C and any point in T (it sounds like you already have this). Create a graph with a vertex for each point in C, and a vertex for each point in T, and an edge between every pair of vertices from different sets (i.e., one from C, one from T) having weight equal to the cost between them, and run one of the several algorithms described on that page, e.g., the Hungarian algorithm, which can be implemented to run in $O(n^3)$ time though the description on that page is only $O(n^4)$. As this might be tricky to implement, I would suggest instead setting up a linear program and using a freely available LP solver to solve it.