<p>Nearest neighbor searches in kd-trees run in logarithmic time, as shown by <a href="https://homes.di.unimi.it/righini/Didattica/AlgoritmiEuristici/MaterialeAE/Friedman%20k-d%20trees.pdf" rel="nofollow noreferrer">Friedman et al.</a> However, I have some difficulty to fully understand the proof.</p>

<blockquote>
  <p>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 <span class="math-container">$S_m(X_q)$</span>.</p>
</blockquote>

<p><span class="math-container">$S_m(X_q)$</span> is the smallest ball centered at the query point <span class="math-container">$X_q$</span> that exactly contains the <span class="math-container">$m$</span> points closest to <span class="math-container">$X_q$</span>.</p>

<p>I don’t get why only the regions overlapping <span class="math-container">$S_m(X_q)$</span> are examined. Consider the following example, where we want to compute the black point that is closest to the orange point <span class="math-container">$X_q$</span>. <span class="math-container">$S_m(X_q)$</span> is the green circle in this case, so according to the proof the algorithm should only search both lower buckets.</p>

<p><a href="https://i.sstatic.net/btfF4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/btfF4.png" alt="enter image description here"></a></p>

<p>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.</p>

<p>So, isn't it too restricted to compute only the buckets that intersect the green circle?</p>

CC BY-SA 4.0
2020-01-25T15:51:49.627Z
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.
user1494080
CC BY-SA 4.0
2020-01-25T19:58:43.120Z
Have you considered more modern algorithms? See, for example, the references in our paper: https://arxiv.org/abs/1910.05270
Aryeh
CC BY-SA 4.0
2020-01-27T15:50:23.323Z
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.
user1494080
CC BY-SA 4.0
2020-01-28T18:35:24.033Z
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.
JimN
CC BY-SA 4.0
2020-01-28T22:52:42.380Z
@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.
user1494080
<ds.algorithms><ds.data-structures><cg.comp-geom><near-neighbors>
Time Complexity for Nearest Neighbor Searches in kd-trees
user1494080
# Time Complexity for Nearest Neighbor Searches in kd-trees

(Asked by: username_0 on 2020-01-25)

Nearest neighbor searches in kd-trees run in logarithmic time, as shown by [Friedman et al.](https://homes.di.unimi.it/righini/Didattica/AlgoritmiEuristici/MaterialeAE/Friedman%20k-d%20trees.pdf) 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](https://i.sstatic.net/btfF4.png)](https://i.sstatic.net/btfF4.png)

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?

**Tags:** ds.algorithms, ds.data-structures, cg.comp-geom, near-neighbors

> **Comments:**
> **username_0**: 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.  
> **username_1**: Have you considered more modern algorithms? See, for example, the references in our paper: https://arxiv.org/abs/1910.05270  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: @username_2 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.  

---

## 0 answers

