In many discussions the directions of the edges are ignored and the NNG is defined as an ordinary (undirected) graph. However it is necessary to keep in mind that the nearest neighbor relation is not a symmetric one, i.e., p from the definition is not necessary a nearest neighbor for q.
In some discussions, in order to make the nearest neighbor for each object unique, the set P is indexed and in the case of a tie the object with, e.g., the largest index is taken for the nearest neighbor.
The k-nearest neighbor 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 k-th smallest among the distances distances from p to other objects from P
The NNG' is a special case of the k-NNG, namely it is the 1-NNG.
Another special case is the (n − 1)-NNG This graph is called the furthest neighbor graph (FNG, sometimes spelled '''farthest neighbor graph).
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 bear in mind that this is not always the case.
NNGs for points in the plane as well as in multidimensional spaces find applications, e.g., in statistical analysis, data compression, motion planning, and facilities location. they are also a subject of computational geometry.
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 a zero-length edge.
Unless stated otherwise, it is assumed that the NNGs are digraphs with uniquely defined nearest neighbors as described in the introduction.