2
$\begingroup$

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.

enter image description here

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ I posted this question two and a half months ago on cs.se. Despite some upvotes, however, there weren't any answers. Maybe it fits better here. $\endgroup$ – user1494080 Jan 25 '20 at 15:51
  • $\begingroup$ Have you considered more modern algorithms? See, for example, the references in our paper: arxiv.org/abs/1910.05270 $\endgroup$ – Aryeh Jan 25 '20 at 19:58
  • $\begingroup$ Well I guess that’s not the point of the question. I want to verify/understand the time complexity proof for nearest neighbor searches in kd-trees. $\endgroup$ – user1494080 Jan 27 '20 at 15:50
  • $\begingroup$ What makes you think it searches the regions that intersect the blue circle? As you point out, the green circle only intersects the lower two quadrants, and these are the only buckets searched. $\endgroup$ – JimN Jan 28 '20 at 18:35
  • $\begingroup$ @JimN The algorithm will find as first candidate solution the black point in the lower right region, because it first descents into the region which contains the query point. Then, it starts back-tracking the path from the source to the region containing the query point. The very next operation the algorithm performs is to check if it has to descent into the upper-left region. Since there could be points in the upper-left region that are closer to the query point than the current tentative solution, the algorithm descents into the upper-left region. $\endgroup$ – user1494080 Jan 28 '20 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.