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 calc...