# Optimal pairing of points in a set

I have an even number of points, each with coordinates $(x, y, z)$. I need to group these points into pairs. The cost of pairing two points is the Euclidean distance between them. I'd like to find the optimal pairing such that the total cost is minimized. What would be a good way/algorithm to solve this?

For example, if you have points $\{a, b, c, d\}$, one possible pairing might be $\{a,d\}, \{b,c\}$. Points can only belong to a single pair.

My Ideas:
The problem seems similar to finding the minimum weighted bipartite matching for a graph. However, I'm not trying to match between two sets of points, just find pairs in a single set. It seems like you might be able to convert this problem to a bipartite graph by duplicating the set of points. This doesn't seem like the right way to do it though (seems like you'd be solving for each pair twice).

You could solve it using an algorithm for weighted matching on general graphs. Just convert the set of points to a complete graph (drawing edges between all possible pairs). It doesn't seem like those algorithms were designed to solve this kind of problem, though (I could be wrong though). So I can't help but wonder if there is a better way to do it.

• I'm wondering if 2-opt would solve this. (generate an arbitrary pair, then keep optimizing until each pair of pairs is optimal) Dec 20, 2016 at 23:25
• That might be something to look into. I'm thinking the "stable roommates problem" is the right direction; though, I can't say for sure whether "stable" translates over to minimum total cost. Dec 21, 2016 at 3:39
• Okay, I found out this problem is commonly called "minimum weighted euclidean matching" in academic literature. Seems like there are specialized algorithms that have O(log(n)*n^2) complexity. Dec 21, 2016 at 6:14
• Cool! Would you like to write an answer to your own question, where you summarize the most important result(s) and give one or more citations to research papers where those results are presented?
– D.W.
Dec 21, 2016 at 7:07
• Sure; I have to read through the technical papers first. Dec 21, 2016 at 18:08

This problem is the 3-dimensional variant of the Euclidean min-cost perfect matching problem (MCPM), and I don't know if it has been studied. The general problem (min-cost maximum-cardinality matching) can be solved in time $$O(\sqrt n \cdot m )$$ [^1].
However, the 2-dimensional version can be solved in time $$O(n^{3/2} \log^5 n)$$. Reading the article by Varadarajan [^2], I cannot see any issues lifting the result to 3-dimensional points.