Mapping a set of 3D points to another set with minimal sum of distances

Question

Given are two sets of three-dimensional points, a source and a destination set. The number of points on each set is arbitrary (may be zero). The task is to assign one or no source point to every destination point, so that the sum of all distances is minimal. If there are more source than destination points, the additional points are to be ignored.

There is a brute-force solution to this problem, but since the number of points may be big, it is not feasible. I heard this problem is easy in 2D with equal set sizes, but sadly these preconditions are not given here.

I'm interested in both approximations and exact solutions.

Edit: Haha, yes, I suppose it does sound like homework. Actually, it's not. I'm writing a program that receives positions of a large number of cars and i'm trying to map them to their respective parking cells. :)

Answer 1

One way you could approach this problem is to treat is as the classical assignment problem: http://en.wikipedia.org/wiki/Assignment_problem

You treat the points as the vertices of the graph, and the weights of the edges are the distance between points. Because the fastest algorithms assume that you are looking for maximum matching (and not minimum as in your case), and that the weights are non-negative, you can redefine weights to be e.g.:

weight(A, B) = bigNumber- distance(A,B)

where bigNumber is bigger than your longest distance.

Obviously you end up with a bipartite graph. Then you use one of the standard algorithms for maximum weighted bipartite matching (lots of resources on the web, e.g. http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/27_matchings_notes.pdf or Wikipedia for overview: http://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings) This way you will end-up with a O(NM max(N,M)) algoritms, where N and M are sizes of your sets of points.

Answer 2

Off the top of my head, spatial sort followed by simulated annealing.

Grid the space & sort the sets into spatial cells.

Solve the O(NM) problem within each cell, then within cell neighborhoods, and so on, to get a trial matching.

Finally, run lots of cycles of simulated annealing, in which you randomly alter matches, so as to explore the nearby space.

This is heuristic, getting you a good answer though not necessarily the best, and it should be fairly efficient due to the initial grid sort.