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

Martin Skrodzki

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 introdu…