Граф ближайших соседей

Граф ближайших соседей с 100 точками на евклидовой плоскости.

Граф ближайших соседей (ГБС) для множества P, состоящего из n объектов в метрическом пространстве (например, для множества точек на плоскости с евклидовой метрикой) — это ориентированный граф, вершинами которого служат элементы множества P, в котором существует ориентированное ребро из p в q, если q является ближайшим соседом p (т.е. расстояние от p до q не больше, чем от p до любого другого объекта из P)[1].

Во многих обсуждениях направление рёбер игнорируется и ГБС определяется как обычный (неориентированный) граф. Однако отношение ближайшего соседства не является симметричным, т.е. если q является ближайшим соседом p, то p не обязательно будет ближайшим соседом q.

В некоторых обсуждениях, чтобы сделать выбор ближайшего соседа единственным, множество P индексируется и когда происходит выбор ближайшего объекта, выбирается объект с наибольшим индексом[2].

Граф k-ближайших соседей (k-ГБС) — это граф, в котором две вершины p и q связаны ребром, если расстояние между p и q находится среди k наименьших расстояний от p до других объектов в P. ГБС является частным случаем k-ГБС, а именно, это 1-ГБС. k-ГБС удовлетворяют условиям теоремы о планарном разбиении — их можно разбить на два подграфа с максимум ${\displaystyle {\tfrac {n(d+1)}{d+2}}}$ вершинами путём удаления ${\displaystyle \mathrm {O} (k^{\tfrac {1}{d}}n^{1-{\tfrac {1}{d}}}}$) точек[3].

Другой частный случай — (n − 1)-ГБС. Этот граф называется графом дальних соседей (ГДС).

В теоретических обсуждениях алгоритмов часто предполагается некий вид общего положения, а именно, что для каждого объекта ближайший (k-ближайший) сосед единственен. При имплементации алгоритмов необходимо учитывать, что это условие не всегда выполняется.

ГДС как для точек на плоскости, так и для точек в многомерных пространствах, находят приложения, например, в сжатии данных, для планирование движения^[англ.] и размещения объектов. В статистическом анализе алгоритм цепей ближайших соседей^[англ.], основанный на путях в этом графе, может быть использовано для быстрого поиска иерархических кластеризаций. Графы ближайших соседей являются также предметом вычислительной геометрии.

Графы ближайших соседей для множеств точек

Одномерный случай

Для множества точек на плоскости ближайшим соседом точки является левый или правый (или оба) сосед, если они отсортированы вдоль прямой. Таким образом, ГБС является путём или лесом нескольких путей и может быть построен за время O(n log n) путём сортировки. Эта оценка является асимптотически оптимальной^[англ.] для некоторых моделей вычислений, поскольку построенный ГБС даёт ответ задачи уникальности элементов^[англ.] — достаточно проверить, нет ли в полученном ГБС ребра нулевой длины.

Более высокие размерности

Если нет явного указания, предполагается, что графы ближайших соседей являются ориентированными графами с единственным образом определённым соседями, как описано во введении.

1. Вдоль любого ориентированного пути в ГБС длины рёбер не увеличиваются[2].
2. Возможны циклы лишь длины 2 в ГБС и каждая слабо связная компонента ГДС с 2 и более вершинами имеет в точности один 2-цикл[2].
3. Для точек плоскости ГБС является планарным графом со степенями вершин, не превосходящими 6. Если точки находятся в общем положении, степень вершин не превосходит 5[2].
4. ГБС (рассматриваемый как неориентированный граф с разрешением нескольких ближайших соседей) множества точек плоскости или любого пространства более высокой размерности является подграфом триангуляции Делоне, графа Габриэля и полуяова графа^[англ.][4]. Если точки находятся в общей позиции или если наложено условие единственности ближайшего соседа, ГБС является лесом, подграфом евклидова минимального остовного дерева^[англ.].

Примечания

1. Препарата, Шеймос, 1989.
2. Eppstein, Paterson, Yao, 1997, с. 263–282.
3. Miller, Teng, Thurston, Vavasis, 1997.
4. Rahmati, King, Whitesides, 2013, с. 137–144.

Литература

• Ф. Препарата, М. Шеймос. Высислительная геометрия: Введение. — Москва: «Мир», 1989. — ISBN 5-03-001041-6 УДК 681.3 513.
• D. Eppstein, M. S. Paterson, Frances Yao. On nearest-neighbor graphs // Discrete and Computational Geometry. — 1997. — Т. 17, вып. 3. — С. 263–282. — doi:10.1007/PL00009293.
• Gary L. Miller, Shang-Hua Teng, William Thurston, Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs // J. ACM. — 1997. — Т. 44, вып. 1. — С. 1–29. — doi:10.1145/256292.256294.
• Z. Rahmati, Valerie King, S. Whitesides. Kinetic data structures for all nearest neighbors and closest pair in the plane // Proceedings of the 29th ACM Symposium on Computational Geometry. — 2013. — С. 137–144. — doi:10.1145/2462356.2462378.

Ссылки

• C++ library for efficient nearest-neighbor graph construction Архивная копия от 23 января 2021 на Wayback Machine