# The k-d tree data structure and a proof for neighborhood computation in expected logarithmic time

arXiv: https://arxiv.org/abs/1903.04936 · HTML: https://mlsanity.com/paper/1903.04936/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2019.

## Built on by (most cited first, 3 of 3)

- [Autonomous Hiking Trail Navigation via Semantic Segmentation and Geometric Analysis](https://mlsanity.com/paper/2409.15671/) (2024)
- [Automated Road Extraction and Centreline Fitting in LiDAR Point Clouds](https://mlsanity.com/paper/2502.07486/) (2025)
- [CONFEX: Uncertainty-Aware Counterfactual Explanations with Conformal Guarantees](https://mlsanity.com/paper/2510.19754/) (2025)

## Abstract (arXiv)

For practical applications, any neighborhood concept imposed on a finite point set P is not of any use if it cannot be computed efficiently. Thus, in this paper, we give an introduction to the data structure of k-d trees, first presented by Friedman, Bentley, and Finkel in 1977. After a short introduction to the data structure (Section 1), we turn to the proof of efficiency by Friedman and his colleagues (Section 2). The main contribution of this paper is the translation of the proof of Freedman, Bentley, and Finkel into modern terms and the elaboration of the proof.