Граф ближайших соседей (Ijgs Qln'gwon] vkvy;yw)
Граф ближайших соседей (ГБС) для множества 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-ГБС удовлетворяют условиям теоремы о планарном разбиении — их можно разбить на два подграфа с максимум вершинами путём удаления ) точек[3].
Другой частный случай — (n − 1)-ГБС. Этот граф называется графом дальних соседей (ГДС).
В теоретических обсуждениях алгоритмов часто предполагается некий вид общего положения, а именно, что для каждого объекта ближайший (k-ближайший) сосед единственен. При имплементации алгоритмов необходимо учитывать, что это условие не всегда выполняется.
ГДС как для точек на плоскости, так и для точек в многомерных пространствах, находят приложения, например, в сжатии данных, для планирование движения и размещения объектов. В статистическом анализе алгоритм цепей ближайших соседей , основанный на путях в этом графе, может быть использовано для быстрого поиска иерархических кластеризаций. Графы ближайших соседей являются также предметом вычислительной геометрии.
Графы ближайших соседей для множеств точек[править | править код]
Одномерный случай[править | править код]
Для множества точек на плоскости ближайшим соседом точки является левый или правый (или оба) сосед, если они отсортированы вдоль прямой. Таким образом, ГБС является путём или лесом нескольких путей и может быть построен за время O(n log n) путём сортировки. Эта оценка является асимптотически оптимальной для некоторых моделей вычислений, поскольку построенный ГБС даёт ответ задачи уникальности элементов — достаточно проверить, нет ли в полученном ГБС ребра нулевой длины.
Более высокие размерности[править | править код]
Если нет явного указания, предполагается, что графы ближайших соседей являются ориентированными графами с единственным образом определённым соседями, как описано во введении.
- Вдоль любого ориентированного пути в ГБС длины рёбер не увеличиваются[2].
- Возможны циклы лишь длины 2 в ГБС и каждая слабо связная компонента ГДС с 2 и более вершинами имеет в точности один 2-цикл[2].
- Для точек плоскости ГБС является планарным графом со степенями вершин, не превосходящими 6. Если точки находятся в общем положении, степень вершин не превосходит 5[2].
- ГБС (рассматриваемый как неориентированный граф с разрешением нескольких ближайших соседей) множества точек плоскости или любого пространства более высокой размерности является подграфом триангуляции Делоне, графа Габриэля и полуяова графа[4]. Если точки находятся в общей позиции или если наложено условие единственности ближайшего соседа, ГБС является лесом, подграфом евклидова минимального остовного дерева .
Примечания[править | править код]
- ↑ Препарата, Шеймос, 1989.
- ↑ 1 2 3 4 Eppstein, Paterson, Yao, 1997, с. 263–282.
- ↑ Miller, Teng, Thurston, Vavasis, 1997.
- ↑ 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
Для улучшения этой статьи желательно:
|