algorithm - Closest pair of points across a line -

i have 2 sets of 2d points, separated each other line in plane. i'd efficiently find pair of points, consisting of 1 point each set, minimum distance between them. there's convenient looking paper radu litiu, closest pair 2 separated sets of points, uses l1 (manhattan) distance metric instead of euclidean distance.

does know of similar algorithm works euclidean distance?

i can see extension of standard divide & conquer closest pair algorithm -- divide 2 sets median line perpendicular original splitting line, recurse on 2 sides, closer pair consisting of 1 point each side of median. if minimal distance recursive step d, companion point on 1 side of median must lie within box of dimensions 2d*d. unlike original algorithm, can't see way bound number of points within box, algorithm whole becomes o(m*n).

any ideas?

evgeny's answer works, it's lot of effort without library support: compute full voronoi diagram plus additional sweep line algorithm. it's easier enumerate both sets of points points voronoi cells intersect separating line, in order, , test pairs of points cells intersect via linear-time merge step.

to compute needed fragment of voronoi diagram, assume x-axis separating line. sort points in set x-coordinate, discarding points larger y other point equal x. begin scanning points in order of x-coordinate, pushing them onto stack. between pushes, if stack has @ least 3 points, p, q, r, r pushed, test whether line bisecting pq intersects separating line after line bisecting qr. if so, discard q, , repeat test new top three. crude ascii art:

case 1: retain q  ------1-2-------------- separating line      /  |   p /   |    \    |     q-------r  case 2: discard q  --2---1---------------- separating line    \ /   p x r    \ /     q