3
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

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