Nearest neighbor graph
Encyclopedia
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 many discussions the directions of the edges are ignored and the NNG is defined as an ordinary (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 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 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.
Another special case is the (n − 1)-NNG. This graph is called the farthest neighbor graph (FNG).
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.
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 clustering
s quickly. Nearest neighbor graphs are also a subject of computational geometry
.
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.
Metric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
(e.g., for a set of points in the plane with Euclidean distance
Euclidean distance
In mathematics, the Euclidean distance or Euclidean metric is the "ordinary" distance between two points that one would measure with a ruler, and is given by the Pythagorean formula. By using this formula as distance, Euclidean space becomes a metric space...
) is a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
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 many discussions the directions of the edges are ignored and the NNG is defined as an ordinary (undirected) graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
. However, the nearest neighbor relation is not a symmetric one
Symmetric relation
In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...
, i.e., p from the definition is not necessarily 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 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
Planar separator theorem
In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices...
: they can be partitioned into two subgraphs of at most vertices each by the removal of O(k1/dn1 − 1/d) points.
Another special case is the (n − 1)-NNG. This graph is called the farthest neighbor graph (FNG).
In theoretical discussions of algorithms a kind of general position
General position
In algebraic geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the general case situation, as opposed to some more special or coincidental cases that are possible...
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.
NNGs for points in the plane as well as in multidimensional spaces find applications, e.g., in data compression
Data compression
In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
, motion planning
Motion planning
Motion planning is a term used in robotics for the process of detailing a task into discrete motions....
, and facilities location. In statistical analysis, the nearest-neighbor chain algorithm
Nearest-neighbor chain algorithm
In the theory of cluster analysis, the nearest-neighbor chain algorithm is a method that can be used to perform several types of agglomerative hierarchical clustering, using an amount of memory that is linear in the number of points to be clustered and an amount of time linear in the number of...
based on following paths in this graph can be used to find hierarchical clustering
Hierarchical clustering
In statistics, hierarchical clustering is a method of cluster analysis which seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two types:...
s quickly. Nearest neighbor graphs are also a subject of computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
.
One dimensional case
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 pathPath (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
or a forest of several paths and may be constructed in O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n log n) time by sorting
Sorting
Sorting is any process of arranging items in some sequence and/or in different sets, and accordingly, it has two common, yet distinct meanings:# ordering: arranging items of the same kind, class, nature, etc...
. This estimate is asymptotically optimal
Asymptotically optimal
In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor worse than the best possible algorithm...
for certain models of computation, because the constructed NNG gives the answer to the element uniqueness problem
Element uniqueness problem
In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct.It is a well studied problem in many different models of computation...
: it is sufficient to check whether the NNG has a zero-length edge.
Higher dimensions
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.
- Only cycles of length 2 are possible in an NNG and each weakly connected component of an NNF with at least 2 vertices has exactly one 2-cycle.
- For the points in the plane the NNG is a planar graphPlanar graphIn graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
with vertex degrees at most 6. If points are in general positionGeneral positionIn algebraic geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the general case situation, as opposed to some more special or coincidental cases that are possible...
, the degree is at most 5. - 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 triangulationDelaunay triangulationIn mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
and the Gabriel graphGabriel graphIn mathematics, the Gabriel graph of a set S of points in the Euclidean plane expresses one notion of proximity or nearness of those points. Formally, it is the graph with vertex set S in which any points P and Q in S are adjacent precisely if they are distinct and the closed disc of which line...
of the pointset. If the points are in general position or if the single nearest neighbor condition is imposed, the NNG is a forestTree (graph theory)In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
, a subgraph of the Euclidean minimum spanning treeEuclidean minimum spanning treeThe Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane , where the weight of the edge between each pair of points is the distance between those two points...
.