Fast way to compute the minimal distance of two sets of k-dimensional vectors

I two sets of k-dimensional vectors, where k is around 500 and the number of vectors is usually smaller. I want to compute the 开发者_C百科(arbitrarily defined) minimal distance between the two sets. A naive approach would be this:

(loop for a in set1
      for b in set2
      minimizing (distance a b))

However, this requires O(n² * distance) computations. Is there a faster way of doing this?

I don't think you can do better than O(n^2) when the distance is arbitrary (you have to examine each of the possible distances!). For a given distance function we might be able to exploit the properties of the function, but there won't be any general algorithm which works with any distance function in better than O(n^2) (i.e. o(n^2) : note smallOh).

If your data is dynamic and you have to keep obtaining the closest pair of points at different times, for arbitrary distance function the following papers by Eppstein will probably help (which have special update operations in order to make finding the closest pair of points quick):

• http://www.ics.uci.edu/~eppstein/projects/pairs/Papers/Epp-SODA-98.pdf. [O(nlog^2(n)) update time]

• http://academic.research.microsoft.com/Paper/1847461.aspx

You will be able to adapt the above one set algorithms to a two set algorithm (for instance, by defining distance between points of same set to be infinity).

For Euclidean type (L^p) distance, there are known O(nlogn) time algorithms, which work with a given set of points (i.e. you dont need to have any special update algorithms):

• http://www.cse.iitd.ernet.in/~ssen/cs852/scribe/scribe2/lec.pdf
• http://en.wikipedia.org/wiki/Closest_pair_of_points_problem

Of course, the L^p is for one set, but you might be able to adapt it for two sets.

If you give your distance function, it might be easier for us to help you.

Hope it helps. Good luck!

If the components of your vectors are scalars I would guess that for your case of a moderate k=500 the O(n²) approach is probably as fast as you can get. You can simplify your calculation by minimizing distance². Also, the distance(A_i, B_i) = distance(B_i, A_i), so make sure you only compare them once (you only have 500!/(500-2)! pairs, not 500²).

If the components are m-dimensional vectors A and B instead, you could store the components of vector A in a R-tree or a kd-tree and then find the closest pair by iterating over all components of vector B and finding its closest partner from A--- this would be O(n). Don't forget that big-O is for n->infinity, so the trees might come with some pretty expensive constant term (i.e. this approach might only make sense for large k or if vector A is always the same).

Put the two sets of coordinates into a Spatial Index, e.g. a KD-tree.

You then compute the intersection of these two indices.