I have 2n random points on a plane. Join pairs of points to make paths. Pair the points such that the summed path length is a minimum. In the picture below, we are trying to minimise the total length of all red-line segments. Points cannot be reused.

Obviously there's the naive brute-force solution, but I wonder if there's a better way. I thought about picking the smallest path then eliminating and picking the next smallest path but then that doesn't guarantee the shortest overall path.

Any pointers welcome. enter image description here

  • $\begingroup$ Does the path need to be connected? Can a point belong to more than one pair? $\endgroup$ – BlueRaja - Danny Pflughoeft Oct 28 '20 at 0:13
  • $\begingroup$ I think I've clarified in an edit - and I've added a diagram of what I mean as well. $\endgroup$ – Ashiataka Oct 28 '20 at 0:27
  • $\begingroup$ This is equivalent to finding closest pair of points and adding the distance between all those pairs. You can always use Divide and Conquer to find the closest pair of points and apply the same algorithm 2n/2 times, eliminating one such pair each time. This could be done in O((n^2)lgn) times, not tightly bounded (upper bound). So, I think we can bring that down to O(n *((lgn)^2)). $\endgroup$ – Ramesses2 Oct 28 '20 at 14:14
  • $\begingroup$ It is absolutely not equivalent. Consider four points on a line at 0, 5, 6, 10. With your method the total length would be (6 - 5) + (10 - 0) = 11. But that is not the solution. The solution is ((5 - 0) + (10 - 6)) = 9. $\endgroup$ – Ashiataka Oct 28 '20 at 15:58

This appears to be a maximum matching problem. Well, minimum matching, but you should be able to make the necessary adaptations.


This is a modification of a maximum matching problem, as answered by DW. Modifying Hopcroft-Karp for this use is a undergrad uni level assignment (one I had to do myself at that level).


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.