# Nearest neighbours with a subset structure

I have a set of points of $$\mathbb{R}^2$$ which is organised in subsets: $$\cup_{0\leq i For all $$(i,j)$$, I want to find $$P_k^l$$ in another subset (with $$k\not= i$$) so that $$d(P_k^l,P_i^j)$$ is minimal. And "of course" (*), many points with $$k=i$$ are in general much closer to $$P_i^j$$ than points with $$k\not=i$$ (**).

Does that evoke any well known variant of nearest neighbour search problems?

If I use a standard R-tree approach, the leaves of search tree will be full of useless $$P_i^l$$ points, for which a costly distance calculation will be performed, and I will then have to filter them out. Of course this shouldn't alter the logarithmic cost in $$O(\log(NM))$$ if leaf size is appropriate, but I expect the constant to be much larger than with a tailored algorithm. Before deciding whether to code my own implementation, I would like to make sure that there aren't classical algorithms that would handle this case efficiently.

Notes: $$N$$ is of order 10, while $$M$$ of order $$10^3$$ to $$10^4$$. I'm using python, currently with scikit learn's nearest neighbour search. (*) Not because it's natural, just because else there wouldn't be a reason to look for a variant algorithm. (**) Estimate is that about 40 points $$P_i^l$$ will in general be closer to $$P_i^j$$ than any $$P_{k\not=i}^m$$ for usual meshing, and this number will increase linearly with mesh refinement. This is because points of a same set discretise a curve of $$\mathbb{R}^2$$, and the $$N$$ curves don't intersect or touch.

• Thanks @Richard. Do you mean: generate a R-tree for each subset $S_k$, then find $P_k^{l_k}$ nearest neighbour of $P_i^j$ for all $i\not=k$? Indeed that sounds good.