The k-dimensional tree (k-d tree) is a binary tree data structure designed for organizing points in a k-dimensional space. Originally introduced by Bentley in 1975 , k-d trees have become a fundamental tool for a range of nearest-neighbor and range-search queries in computational geometry and scientific computing. Suppose there is a set of N points,