nearest neighbor and inverse nearest neighbor

The Nearest Neighbor problem, also known as the Post Office Problem and the Closest Point Problem, can be described as follows: given a set of n data points, we want to preprocess these points so that, given a query point q, we can find the data point closest to q quickly. The k-Nearest Neighbor problem is to preprocess a set of n data points so that the k closest points to a query point q can be found quickly. The Inverse Nearest Neighbor problem is described as follows: given a set S of n data points, we want to preprocess these points so that, for a query point q S, we can quickly determine for which points q is a nearest neighbor. Similarly, the k-inverse nearest neighbor problem is to preprocess the data points so that we can quickly determine for which points q is a k-nearest neighbor.

kd-tree

A multidimensional search tree for points in k dimensional space. Levels of the tree are split along successive dimensions at the points.