# Algorithm to mimimally pair up points in 3D space

Given a set of $n$ points $P$ and a set of $n$ points $Q$ in 3 dimensional space, what's the fastest algorithm to uniquely pair points in $P$ with points in $Q$ so that the sum of the square of the distance between points in $P$ and their corresponding point in $Q$ is minimized? Each point in $P$ must be matched with one and only one point in $Q$, and vice versa.

Another way to look at the problem: if $P$ and $Q$ are matricies with 3 columns and $n$ rows, how can I reorder the rows of $P$ so as to minimize the frobenius norm of $P - Q$?

This problem can be solved in $O(n^3)$ by creating a cost matrix $M$ where $m_{i,j}$ is the distance between point $P_i$ and point $Q_j$, and then by using the hungarian algorithm to find the minimal assignment, however I feel like there's a faster way.

Even if there isn't an exact solution, are there any fast approximations?

Edit: for my specific use-case, the points in $P$ are the points on a $m \times m \times m$ grid and $n=m^3$

• – D.W.
Commented Jul 20, 2017 at 17:08

As an approximate solution in $O(n^2)$ you can construct the cost matrix $M$ and then solve the stable marriage problem.