0
$\begingroup$

I have a set of points of $\mathbb{R}^2$ which is organised in subsets: $$ \cup_{0\leq i<N} \left\{ P_i^j \in \mathbb{R}^2, 0\leq j<M \right\} $$ 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.

$\endgroup$

1 Answer 1

2
$\begingroup$

Make a separate R-tree for each subset. Your NN lookup is then N log(M). If the number of falsely proximal points exceeds N then you might have a time savings versus a single R-tree customized to discriminate by subset. You can also parallelize across N.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joce
    Commented May 2, 2022 at 16:26
  • 1
    $\begingroup$ @JoceNoToPutinsWarInUkraine: that is what I mean. Please circle back if the performance isn't acceptable. $\endgroup$
    – Richard
    Commented May 2, 2022 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.