  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.
