Smallest sum of pairs

Question

Given 2N-points in a 2D-plane, you have to group them into N pairs such that the overall sum of distances between the points of all of the pairs is the minimum possible value.The desired output is only the sum.

In other words, if a1,a2,..an are the distances between points of first, second...and nth pair respectively, then (a1+a2+...an) should be minimum.

Let us consider this test-case, if the 2*5 points are : {20,20}, {40, 20}, {10, 10}, {2, 2}, {240, 6}, {12, 12}, {100, 120}, {6, 48}, {12, 18}, {0, 0}

The desired output is 237.

This is not my homework,I am inquisitive about different approaches rather than brute-force.

Answer 1

Your final sum will mostly be dominated by the largest addend. The simplest algorithm to exploit this could go like this (I cannot prove this):

1. sort points descending by their nearest-neighbor distance
2. form pair of first entry and its nearest neighbor
3. remove pair from list
4. if list not empty goto 1.

This should work very often.

Since you are essentially looking for a clustering algorithm for clusters of 2 this link or a search for clustering algorithms for jet reconstruction might be interesting. People in the experimental particle physics community are working on heuristic algorithms for problems like this.

Answer 2

After googling a while, I found some other references to minimum weight perfect matching algorithms which might be easier to understand (at least, easier to a certain degree).

EDIT

Here I found a python implementation of one of those algorithms. It has 837 lines of code (+ some additional unit tests), and I did not try it out by myself. But perhaps you can use it for your case.

Here is a link to an approximation algorithm for the problem. Of course, the style of the paper is mathematical, too, but IMHO much easier to understand than the paper of Cook and Rohe. And it states in its preface that it aims exactly for the purpose to be easier to implement than Edmond's original algorithm, since you don't need a linear programming solver.

EDIT2:

After thinking a while about the problem, IMHO it must be possible to set up an A* search for solving this problem. The search space here is the set of 'partially matchings' (or partially paired point sets). As Moron already wrote in his comments, one can restrict the search to the situation where no pairs with crossing connecting lines exist. The path-cost function (to use the terms from Wikipedia) is the sum of the distances of the already paired points. The heuristic function h(x) can be any under-estimation for the remaining distances, for example, when you have 2M points not paired so far, take the sum of the M minimal distances between all of those remaining points.

That one will probably be not as efficient as the algorithm Moron pointed to, but I suspect it will be much better than 'brute force', and much easier to implement.