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.
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.
[^1] Micali, Silvio, and Vijay V. Vazirani. &quot;An $O(\sqrt{|v|} \cdot |E|)$ algorithm for finding maximum matching in general graphs.&quot; 21st Annual Symposium on Foundations of Computer Science (sfcs 1980). IEEE, 1980.
[^2] Varadarajan, Kasturi R. &quot;A divide-and-conquer algorithm for min-cost perfect matching in the plane.&quot; Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280). IEEE, 1998.