Find nearest neighbour in a radius

Question

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.

Answer 1

The K-D tree is a good data structure for solving this. However you can't blindly apply the search procedure only to the center point, you must be a bit smarter.

While searching the K-D tree for your points, every time you must choose the left or right child to search in, check whether the splitting plane is to the left of your circle, intersects it, or is to the right of the circle.

If the splitting plane is to the left of your circle you must continue searching in the right child, and vice versa. However when the splitting plane intersects your circle you must search both children.