Minimize sum of distances in point pairs

Question

I have a bunch of points on a 2-dimensional Grid. I want to group the Points into pairs, while minimizing the sum of the euclidean distances between the points of the pairs.

Example:

Given the points: 

p1: (1,1)
p2: (5,5)
p3: (1,3)
p4: (6,6)

Best solution: 
pair1 = (p1,p3), distance = 2
pair2 = (p2,p4), distance = 1
Minimized total distance: 1+2 = 3

I suspect this problem might be solvable with a variant of the Hungarian Algorithm?!

What is the fastest way to solve the problem?

(Little Remark: I always should have less than 12 points.)

Incompetence

Have you tried sorting all possible edged by their length and greedily choosing the shortest ones until you have n/2 edges? Won't find a global minimum in any case but maybe the approximation is enough? Do you have real time constraints? 12 points are not that many and a naive backtracking approach could be sufficient (if the calculation is just performed once). – Authenticity

Homework? It seems similar to the Hungarian Problem, also similar to Graph Traversal and network optimization (shortest path). – Curator

For 12 points you only have to check 10,395 combinations. see math.stackexchange.com/questions/35684/… – Edd

This is exactly the maximum weight matching problem, but you don't need a polynomial time solution since n! is small enough – Petit

For general n, see A new implementation of a minimum cost perfect matching algorithm – Outfall

@ChuckCottrill: i am at a university, but i need it for a project (see my other SO question if you want to see more ;) – Incompetence

@NicoSchertler: Yes, but the case with 4 points at 1,3,4,6 fails, because you get the pairs (3,4) and (1,6). Since this should be fairly common in my program I don't want to risk it. – Incompetence

There is a Dynamic Programming Solution , with O(n^2 * 2^(n)) complexity . – Eicher

@Mod: do you maybe have a link for that? – Incompetence

Ok , I have done a mistake in its analysis , actually it is of O(n^2 * 2^(2n)) complexity do you still need the algorithm ? – Eicher

@Mod: Sure, i would love to have a look at it. (Even if i don't use it somebody else might profit from it in the future!) – Incompetence

Answer 1

The problem you are trying to solve is similar to the shortest path through a fully connected (mesh) network, where you are not allowed to visit each vertex/node more than once, and you don't care about connecting the minimal pairs.

This problem is approachable when using techniques from graph theory, metric spaces, and other results from computational geometry.

This problem is similar the wiki article on the Closest pair of points problem, and the article offers some useful insights regarding Voroni diagrams and Delaunay triangulation, as well as using Recursive Divide and Conquer algorithms to solve the problem.

Note that solving the closest pair of points is not the solution, as you could have four points (A,B,C,D) in a line, where d(B,C) is least, but then you would also have d(A,D), and the sum would be larger than d(A,B) and d(C,D).

This stackoverflow question explains how to find the shortest distance between two points, and has a useful hint to skip computing the square root while comparing distances. Answers suggest using a divide and conquer approach (linear), but observe that splitting both X and Y coordinates might partition more appropriately.

This math stackexchange question addresses a similar problem, and suggests using Prim's algorithm, Kruskal's algorithm, or notes that this is a special case of the Travelling Salesman problem, which is NP-hard.

My approach would be to solve your problem (pairing the closest points) using a greedy algorithm to compute a minimal spanning tree, and then remove from the spanning tree 1/2 the edges (leaving disconnected pairs). Likely using a second (variant) of a greedy algorithm.

Curator

Additionally, simply pruning a Minimum Spanning Tree does not guarantee a result. For some situations, you will be forced to create singletons, depending on the degree of the nodes. – Ury

Answer 2

There are so few pairings possible for 12 or less points (about 10000 or less as pointed out in a comment), you can check all pairings by brute force and even with this solution you can solve about 10000 problems per second with 12 or less points on a modern personal computer. If you want a faster solution, you can enumerate nearest neighbors in order for each point and then just check pairings that are minimal with respect to which nearest neighbors are used for each point. In the worst-case I don't think this gives a speed-up, but for example if your 12 points come in 6 pairs of very close points (where unpaired points are far away) then you'd find the solution very quickly because the minimal pairing with respect to nearest neighbors would match together each point with its first nearest neighbor.

Obituary