So I have two point clouds $X$ and $Y$ each with $N$ points in the familiar $\mathbb{R}^3$ euclidian 3D space. I then have an inter-point distance $d(\vec x_i,\vec y_j)$ which is zero if $\vec x_i$ is equal to $\vec y_j$.
I need to pair up $X$ and $Y$ in such a way that there will be $N$ pairs $(\vec x_i,\vec y_j)$ which minimizes the sum of the distances $d(\vec x_i,\vec y_j)$ for all pairs. Each point $\vec x_i$ and $\vec y_j$ can't show up in more than one pair in the whole set.
This has to be done without rotating any of the clouds relative to each other because these represent samplings from electron densities around a set of atomic nuclei in the Born-Oppenheimer approximation. The nuclei for both clouds are fixed at a specific set of positions and these have to be kepts the same in both clouds, rotations would change that.
Any ideas on how to do that at all? Efficient solutions are preferable, but any solution would be very welcome.
Thanks in advance and Euler bless y'all.
While this question's gone unanswered for six years, I happened to come across it searching for other things. Because X and Y are both of size N, the pairing here is classified as a balanced assignment problem in combinatorial optimization. There are many methods for registering point clouds to each other (e.g. Zhu et al. 2018, Maiseli et al. 2017) but, from the way the question is phrased, it appears the main desire here is to find the best fitting translation in { x, y, z } but, while rotation is prohibited, it's unclear if other operations such as scaling or mirroring would be needed. My inclination, however, is to interpret this as a question about rigid registration rather than nonrigid.
I'm also unsure if the desire is to use an existing tool, write new code, or something else. Assuming the former, R, python, MATLAB, the Point Cloud Library, and Cloud Compare are some common starting points. Most implementations I've used have the ability to disable rotation (and to restrict translation or scaling) but this isn't true in all cases. For algorithms, I would suggest beginning by assessing the RANSAC and iterative closest point families for suitability. The structure and rigidity of the clouds will influence which variants in which family might be of most interest. However, I'm unsure which to suggest as I'm unfamiliar with this particular cloud-to-cloud registration problem.