# finding the $n$ closest pairs between $2n$ points

Given $2n$ points $x_1, x_2 \ldots x_{2n}$ and a distance $d_{i,j}$ defined between them, how can I best find the set $P$ of mutually exclusive pairs $(i,j)$ such that the sum of their distances

$$\sum_{(i,j) \in P} d_{i,j}$$

is minimised? The definition of $d_{i,j}$ is open and the function could be convex. The motivation for this problem is practical. How can I pair of 30 pictures say into most similar pairs?

I apologise in advance for the choice of tags on this post. I have been out of maths proper for a long time.

-

What you're looking for is a minimal weight perfect matching on a complete graph. From a quick wikipedia search, I think Edmonds' matching algorithm will do the trick for you (see the bottom of the page) - I think it's polynomial time in the number of nodes.

-
Many thanks for this. I think that is precisely what I need: it seems to cover the minimisation case as well as the converse maximisation. There is even some code in C++ and Python out there to do it. It also explains by my initial attempts to adapt simpler techniques failed! –  David Dec 3 '11 at 10:36
Thanks, Igor. I will only add that there are citations under "Problem 6: Minimum Euclidean Matching in 2D" to papers that describe an exact algorithm that runs in about $O(n^{3/2})$, and $(1 + \epsilon)$ approximation algorithms. –  Joseph O'Rourke Dec 3 '11 at 13:27
@Igor: I'm slightly confused about "Euclidean". The OP says that the definition of $d_{ij}$ is open, so it could be non-Euclidean too? –  Suvrit Dec 4 '11 at 11:11