Find close-enough points in 3d space

Question

I have 2 sets of points in 3d space , each set of size n.

I need to calc. all the points from the first set the are close enough (dist between 2 points < TH, TH is given) to at least one of the points from the second set. Note that the calc might result in empty set.

Doing this in O(n^2) is easy. my q - is there a better one ? nlog^2n maybe like "closest pair of point" algorithm ?

thanks for the help, Best danny.

Answer 1

One approach is to build an R-tree for one of the sets and then query this tree for all points in the other set. I would expect something close to amortized $O(n \log n)$ but I do not know what the worst case could be.