Nearest pair of dots 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 points that two drew lines, I want the two points to allow me to draw the shortest line segment between two lines.

Looking around, almost everything seems to be dealing with finding the nearest points in 1 set. Although I found one solution recommending voronoi tesselation for a start, which seems a bit like overkill, I'm just looking for something more enjoyable than O (n ^ 2).

If this helps, the two sets compare string strings, although they are not necessarily straight, and I am writing this in C #.

Thanks.

Answer 1

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

The merge step must be changed to accept the selected pairs from left to right with a member from only each set. Thus, the recursive function will return the nearest pair AB. The behavior of O (N.Log (N)) must be preserved.

If the said “lines” have a well-known equation, so that the distances between points / lines (or even the intersections of lines / lines) can be quickly estimated, there may be faster solutions.