Граф ближайших соседей ( NNG ) — это ориентированный граф, определенный для множества точек в метрическом пространстве , например, евклидово расстояние на плоскости . NNG имеет вершину для каждой точки и направленное ребро от p до q , когда q является ближайшим соседом p , точкой, расстояние от которой до p является минимальным среди всех заданных точек, отличных от самой p . [1]
Во многих случаях использования этих графов направления ребер игнорируются, и вместо этого NNG определяется как неориентированный граф . Однако отношение ближайшего соседа не является симметричным , т. е. p из определения не обязательно является ближайшим соседом для q . В теоретических обсуждениях алгоритмов часто предполагается своего рода общее положение , а именно, ближайший (k-ближайший) сосед уникален для каждого объекта. При реализации алгоритмов необходимо иметь в виду, что это не всегда так. Для ситуаций, в которых необходимо сделать ближайшего соседа для каждого объекта уникальным, множество P может быть проиндексировано, и в случае связи объект, например, с наибольшим индексом, может быть взят в качестве ближайшего соседа. [2]
Граф k -ближайших соседей ( k -NNG ) — это граф, в котором две вершины p и q соединены ребром, если расстояние между p и q входит в число k -х наименьших расстояний от p до других объектов из P. NNG является частным случаем k -NNG, а именно, это 1-NNG. k -NNG подчиняются теореме о разделителе : их можно разбить на два подграфа, каждый из которых содержит не более n ( d + 1)/( d + 2) вершин, удалив O( k 1/ d n 1 − 1/ d ) точек. [3] K - NNG можно аппроксимировать с помощью эффективного алгоритма с 90%-ной полнотой, который на порядок быстрее, чем поиск методом перебора. [ 4]
Другой вариант — граф дальних соседей (FNG), в котором каждая точка соединена ребром с самой дальней от нее точкой, а не с ближайшей.
NNG для точек на плоскости, а также в многомерных пространствах находят применение, например, в сжатии данных , планировании движения и расположении объектов . В статистическом анализе алгоритм цепочки ближайших соседей , основанный на отслеживании путей в этом графе, может использоваться для быстрого поиска иерархических кластеров . Графы ближайших соседей также являются предметом вычислительной геометрии .
Метод можно использовать для построения графа на узлах с неизвестной связностью.
Для набора точек на прямой ближайшим соседом точки является ее левый или правый (или оба) соседа, если они отсортированы вдоль прямой. Таким образом, NNG представляет собой путь или лес из нескольких путей и может быть построен за время O ( n log n ) путем сортировки . Эта оценка асимптотически оптимальна для определенных моделей вычислений , поскольку построенный NNG дает ответ на проблему уникальности элемента : достаточно проверить, имеет ли NNG ребро нулевой длины. [5]
Если не указано иное, предполагается, что NNG представляют собой орграфы с однозначно определенными ближайшими соседями, как описано во введении.