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.)

Answer 1

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.

Answer 2

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.