Min Cost Flow Optimized for a Complete Bipartite Matching in Euclidean Space

An answer to this question on Stack Overflow.

Question

The gist is... we have two sets of points A and B. Set A and B have the same number of points n.

Formal Problem:

Construct a minimum cost complete bipartite matching between points in A and B. The cost of a matching (a, b) is the distance(a, b). Does there exist an algorithm faster than O(n^3)?

Notes:

  • Every point a in A and point b in B is in a matching (a, b).
  • Every point a in A or B is in exactly one matching.
  • sum( distance(a, b) for every (a, b) matching ) is minimized.

Example:

  • Point a (0,0)
  • Point b (2,0)
  • Point c (0,1)
  • Point d (-2,2)
  • Set Z {a, d}
  • Set Y {b, c}

Solution:

Matching 1: (a, b) (d, c)

sum(distance(a, b), distance(d, c)) = 2 + sqrt(5) ~ 4.23

Matching 2: (a, c) (d, b)

sum(distance(a, c), distance(d, b)) = 1 + sqrt(20) ~ 5.47

Matching 1 (a, b) (d, c) is the min cost complete bipartite matching!

Answer

Yes. If the distances between vertices are taken as the weights of the edges between them, then this is a weighted bipartite graph. The task of finding the maximum/minimum weight matching is known as the assignment problem.

The problem can be solved in O(|V|(|E|+|V| log |V|) time using methods developed in Fredman and Tarjan (1987).

There are further improvements possible in Euclidean spaces. As discussed here. Notably, Vaidya (1988) presents a O(n² log n) algorithm for the L1, L2, and L∞ metrics which improves to O(n² (log n)³) for the L1 and L∞ metrics. Agarwal, Efrat, and Sharir (2006, Section 7) improve on this, giving an algorithm that runs in O(n^(2+ε)) time.

You can do even better if you sacrifice exactness. Agarwal and Varadarajan (2004) present a probabilistic algorithm which, given a value 0<ε<1, finds in O(n^(1+ε)) time a matching with expected cost within a multiplicative O(log(1/ε)) of the optimal.

Do your points happen to lie on the edges of a convex polygon? Then Marcotte and Suri (1991) will be of interest: they present an exact O(n log n) algorithm for that. If the polygon is non-convex, but still simple, then you could use their O(n² log n) algorithm in the same paper.