# Find nearest neighbour in a radius

I have a set of points A in my space (geo points but I can assume they are on a 2D plane).

I have another set of points B.

For every point in B I want to find every point in A inside a radius R with center in the considered point from B set.

I did it with KDTree, this provide me a very fast and easy algorithm to create the data structure and find neighbours but it doens't find every point in a radius because it could avoid a path which contains element in my radius but not in the same subset of the radius center.

Minimal example of KDTree failing:

While exploring KDTree the target point (red) is under the line of point number 1. This will proceed to exploration of point under the line, this will miss the real point inside the red point radius. What algorithm or data structure allow 100% correctness?

I know for sure I will performe worse but I am look for a balance between search speed and full correctness.

• I don't understand why K-d trees don't work. I don't understand what you mean by "avoid a path". What path are you referring to? I don't understand what is meant by "not in the same subset of the radius center". Can you edit your question to explain that? Perhaps you can use mathematics to help explain, or give a concrete example? – D.W. Apr 11 at 20:41
• @D.W. minimal example added – Tway101 Apr 12 at 15:45