Nearest neighbor graph
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 n(d + 1)/(d + 2) 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.
NNGs for sets of points
[edit]One-dimensional case
[edit]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]
Higher dimensions
[edit]Unless stated otherwise, it is assumed that the NNGs are digraphs with uniquely defined nearest neighbors as described in the introduction.
- Along any directed path in an NNG the edge lengths are non-increasing.[2]
- Only cycles of length 2 are possible in an NNG and each weakly connected component of an NNG with at least 2 vertices has exactly one 2-cycle.[2]
- For the points in the plane the NNG is a planar graph with vertex degrees at most 6. If points are in general position, the degree is at most 5.[2]
- The NNG (treated as an undirected graph with multiple nearest neighbors allowed) of a set of points in the plane or any higher dimension is a subgraph of the Delaunay triangulation, the Gabriel graph, and the Semi-Yao graph.[6] If the points are in general position or if the single nearest neighbor condition is imposed, the NNG is a forest, a subgraph of the Euclidean minimum spanning tree.
References
[edit]- ^ Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. ISBN 0-387-96131-3. 1st edition; 2nd printing, corrected and expanded, 1988; Russian translation, 1989.
- ^ a b c d Eppstein, D.; Paterson, M. S.; Yao, Frances (1997). "On nearest-neighbor graphs". Discrete and Computational Geometry. 17 (3): 263–282. doi:10.1007/PL00009293.
- ^ Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A. (1997). "Separators for sphere-packings and nearest neighbor graphs". Journal of the Association for Computing Machinery. 44 (1): 1–29. doi:10.1145/256292.256294.
- ^ Dong, Wei; Moses, Charikar; Li, Kai (28 March 2011). "Efficient k-nearest neighbor graph construction for generic similarity measures". Proceedings of the 20th international conference on World wide web. Association for Computing Machinery. pp. 577–586. doi:10.1145/1963405.1963487. ISBN 9781450306324. S2CID 207186093.
- ^ Aggarwal, Alok; Kipnis, Shlomo (August 1988). "Lecture #10, March 10, 1988: Closest pair". In Aggarwal, Alok; Wein, Joel (eds.). Computational Geometry: Lecture Notes for 18.409, Spring 1988. Massachusetts Institute of Technology Laboratory for Computer Science. Observation 1, p. 2.
- ^ Rahmati, Z.; King, V.; Whitesides, S. (2013). Kinetic data structures for all nearest neighbors and closest pair in the plane. Proceedings of the 29th ACM Symposium on Computational Geometry. pp. 137–144. doi:10.1145/2462356.2462378.