3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I'm wondering if 2-opt would solve this. (generate an arbitrary pair, then keep optimizing until each pair of pairs is optimal) $\endgroup$
    – John Dvorak
    Commented Dec 20, 2016 at 23:25
  • $\begingroup$ 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. $\endgroup$
    – Azmisov
    Commented Dec 21, 2016 at 3:39
  • 3
    $\begingroup$ 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. $\endgroup$
    – Azmisov
    Commented Dec 21, 2016 at 6:14
  • 2
    $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Commented Dec 21, 2016 at 7:07
  • $\begingroup$ Sure; I have to read through the technical papers first. $\endgroup$
    – Azmisov
    Commented Dec 21, 2016 at 18:08

1 Answer 1

Reset to default
1
$\begingroup$

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. "An $O(\sqrt{|v|} \cdot |E|)$ algorithm for finding maximum matching in general graphs." 21st Annual Symposium on Foundations of Computer Science (sfcs 1980). IEEE, 1980.

[^2] Varadarajan, Kasturi R. "A divide-and-conquer algorithm for min-cost perfect matching in the plane." Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280). IEEE, 1998.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.