Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof.
In order to calculate the average number of buckets examined by the k-d tree searching algorithm described above, it is necessary to calculate the average number of buckets overlapped by the region $S_m(X_q)$.
$S_m(X_q)$ is the smallest ball centered at the query point $X_q$ that exactly contains the $m$ points closest to $X_q$.
I don’t get why only the regions overlapping $S_m(X_q)$ are examined. Consider the following example, where we want to compute the black point that is closest to the orange point $X_q$. $S_m(X_q)$ is the green circle in this case, so according to the proof the algorithm should only search both lower buckets.
However, the searching algorithm will find as first candidate solution the black point in the lower right region. Then, it will also search regions that intersect the blue circle, in particular the upper right region.
So, isn't it too restricted to compute only the buckets that intersect the green circle?