The nearest neighbor graph (NNG) for a set of n objects P in a metric space (e.g., for a set of points in the plane with Euclidean distance) is a directed graph with P being its vertex set and with a directed edge from p to q whenever q is a nearest neighbor of p (i.e., the distance from p to q is no larger than from p to any other object from P). 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.