Closest pair of points from two sets, one from each

Question

I have two sets of points, A and B, and I'm trying to find the closest pair of points where one point is taken from each set. That is, if you were to use the points two draw to lines, I want the two points that allow me to draw the shortest line segment between the two lines.

Looking around, almost everything seems to deal with finding the closest points in 1 set. Although I did find one solution recommending voronoi tesselation to begin with, which seems a bit like overkill, I'm just looking for something a bit nicer than O(n^2).

If it helps, the two sets I'm comparing form lines, although they are not necessarily straight and I'm writing this in C#.

Thanks.

Answer 1

It should be possible to adapt the classical D&C algorithm (as described in the Wikipedia link), by processing all points together and tagging them with an extra bit.

The merging step needs to be modified to accept candidate left-right pairs with a member from every set only. This way, the recursive function will return the closest A-B pair. The O(N.Log(N)) behavior should be preserved.

If the "lines" you mention have a known equation so that point/line distances (or even line/line intersections) can be evaluated quickly, there could be faster solutions.