Planar nearest neighbor search for many points.

Question

I have two sets of points on the plane, A and B. For every point in A, I would like the k nearest points in B. The naive approach is for each point in A having a linear selection to choose the kth nearest point. This runs in |A||B| time. What is a faster algorithm of doing this? Note: I also have a tight bound on the points.