The nearest neighbor graph (NNG) is a directed graph defined for a set of points in a metric space, such as the Euclidean distance in the plane. The NNG has a vertex for each point, and a directed edge from p to q whenever q is a nearest neighbor of p, a point whose distance from p is minimum among all the given points other than p itself.[1]
In many uses of these graphs, the directions of the edges are ignored and the NNG is defined instead as an undirected graph. However, the nearest neighbor relation is not a symmetric one, i.e., p from the definition is not necessarily a nearest neighbor for q. In theoretical discussions of algorithms a kind of general position is often assumed, namely, the nearest (k-nearest) neighbor is unique for each object. In implementations of the algorithms it is necessary to bear in mind that this is not always the case. For situations in which it is necessary to make the nearest neighbor for each object unique, the set P may be indexed and in the case of a tie the object with, e.g., the largest index may be taken as the nearest neighbor.[2]
The k-nearest neighbors graph (k-NNG) is a graph in which two vertices p and q are connected by an edge, if the distance between p and q is among the k-th smallest distances from p to other objects from P. The NNG is a special case of the k-NNG, namely it is the 1-NNG. k-NNGs obey a separator theorem: they can be partitioned into two subgraphs of at most vertices each by the removal of O(k1/dn1 - 1/d) points.[3] A k-NNG can be approximated using an efficient algorithm with 90% recall that is faster than a brute-force search by an order of magnitude.[4]
Another variation is the farthest neighbor graph (FNG), in which each point is connected by an edge to the farthest point from it, instead of the nearest point.
NNGs for points in the plane as well as in multidimensional spaces find applications, e.g., in data compression, motion planning, and facilities location. In statistical analysis, the nearest-neighbor chain algorithm based on following paths in this graph can be used to find hierarchical clusterings quickly. Nearest neighbor graphs are also a subject of computational geometry.
The method can be used to induce a graph on nodes with unknown connectivity.
For a set of points on a line, the nearest neighbor of a point is its left or right (or both) neighbor, if they are sorted along the line. Therefore, the NNG is a path or a forest of several paths and may be constructed in O(n log n) time by sorting. This estimate is asymptotically optimal for certain models of computation, because the constructed NNG gives the answer to the element uniqueness problem: it is sufficient to check whether the NNG has a zero-length edge.[5]
Unless stated otherwise, it is assumed that the NNGs are digraphs with uniquely defined nearest neighbors as described in the introduction.