How do tree searches deal with edge errors in nearest-neighbor searches?

Question

Concerning tree searching algorithms, particularly quad-tree and r-tree, how do they account for edge errors when finding nearest neighbors. I'm not good at explaining this with words so I made some pictures.

For the picture the input coordinate to find the nearest neighbor is green, what I would assume end up being the "found" nearest neighbor is red. The actual nearest neighbor is blue.

In this quad-tree, the blue lower-right quadrant would be searched in with only that one red point while in actuality, the input coordinate (green) is so close to the edge it's actually closer to the blue point.

Similar with an R-tree if the coordinate is within one rectangle but so close to the edge it's closer to a point in another rectangle like below, where white dot is given coordinate:

It's wholly within the red box but closer to a point in the magenta box.

Answer 1

In both cases it is necessary to do a fine-grain distance check between elements - the boxes or divisions just help find candidates for the real distance check.

A way to look at it is, use the boxes to tell you what NOT to check. If an entire box is farther away than something you already know, you don't need to check anything in that box. If some of the box is close, better check the elements in it.

Answer 2

If you would bother to read the R-tree publication...

It uses a minimum distance, of the query point to a neighboring page.

If mindist(query, rectangle) <= dist(query, known neighbor) then the search needs to continue in the other rectangle, because there could be a better neighbor there.

It's actually quite straightforward, and should be explained in any book on R-trees and similar indexes.