Minimum sum of distances between pairs

[mehmetinal]

Hello,

The problem is this:

Suppose we have two sets of points (each size N) and we want to find the minimum total sum among all combinations of pairwise matchings.

for example:
If A={a1,a2,a3,a4} and B={b1,b2,b3,b4}

the combinations are:

(a1,b1),(a2,b2),(a3,b3),(a4,b4)
(a1,b2),(a2,b1),(a3,b3),(a4,b4)
(a1,b2),(a2,b3),(a3,b2),(a4,b4)
...etc

I want to find the one with minimum sum of pairwise distances.

Can anybody suggest an efficient algorithm? (O(NlogN or N^2))?

Maybe it's simple but I can't think of a solution right now.

It's part of a problem I am trying to solve, not the whole problem.

Thanks.

[leppyr64]

Can you make a concrete example? You talk abouts sets of points and then list two arrays of values. I don't really understand what it is that you need to accomplish.

[mehmetinal]

Okay, I'll try to be more clear.

A and B are two arrays of points, with x and y coordinates.

A={a1,a2,a3,a4} and B={b1,b2,b3,b4}

a1..a4 and b1..b4 are points with x and y coordinates.

a1 = (xa1, ya1), a2=(xa2,ya2) ... etc

I am trying to find the minimum sum

dist(ai,bj)+dist(ak,bl)+dist(am,bn)+dist(ap,bq)

where i, k, m, p are different indices between 1 and 4, and j, l, n, q are different indices between 1 and 4.

[mehmetinal]

By the way, the distances are Manhattan distances...

[leppyr64]

The algorithm that comes to mind would be to find the minimum-cost maximum flow. You will add edges from every node in A to every edge in B. The capacity of each edge will be 1 and the cost will be the distance between the two nodes. You will also need to add a source and a sink. The source will have edges with capacity 1 and cost 0 to all nodes in A. Sink connects to B.