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.