Граф найближчих сусідів

Граф найбли́жчих сусі́дів (ГНС) для множини P, що складається з n об'єктів у метричному просторі (наприклад, для множини точок на площині з евклідовою метрикою) — орієнтований граф, вершинами якого є елементи множини P, в якому існує орієнтоване оебро з p в q, якщо q є найближчим сусідом p (тобто відстань від p до q не більша, ніж від p до будь-якого іншого об'єкта з P).

Граф найближчих сусідів зі 100 точками на евклідовій площині

У багатьох обговореннях напрямок ребер нехтують та ГНС визначають як звичайний (неорієнтований) граф. Проте відношення найближчого сусідства не є симетричним, тобто, якщо q є найближчим сусідом p, то p не обов'язково є найближчим сусідом q.

У деяких обговореннях, щоб зробити вибір найближчого сусіда єдиним, множину P індексують і коли відбувається вибір найближчого об'єкта, вибирають об'єкт із найбільшим індексом.

Граф 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}}}}$) точок.

Інший окремий випадок — (n − 1)-ГНС. Цей граф називається графом далеких сусідів (ГДС).

У теоретичних обговореннях алгоритмів часто передбачається певний вид загального положення, а саме, що для кожного об'єкта найближчий (k-найближчий) сусід єдиний. При імплементації алгоритмів слід ураховувати, що ця умова не завжди виконується.

ГНС як для точок на площині, так і для точок у багатовимірних просторах, застосовують, наприклад, у стисканні даних, для планування рухів і розміщення об'єктів. У статистичному аналізі ^[en], заснований на шляхах у цьому графі, можна використати для швидкого пошуку ієрархічних кластеризацій. Графи найближчих сусідів є також предметом обчислювальної геометрії.

Графи найближчих сусідів для багатьох точок

Одновимірний випадок

Для множини точок на прямій найближчим сусідом точки є лівий або правий (або обидва) сусіди, якщо вони відсортовані вздовж прямої. Таким чином, ГНС є шляхом або лісом декількох шляхів і його можна побудувати за час O(n log n) шляхом сортування. Ця оцінка є ^[en] для деяких моделей обчислень, оскільки побудований ГНС дає відповідь для задачі ^[en] — достатньо перевірити, чи немає в отриманому ГНС ребра нульової довжини.

Вищі розмірності

Якщо немає явної вказівки, передбачається, що графи найближчих сусідів є орієнтованими графами з єдиним способом визначеними сусідами, як описано у вступі.

1. Уздовж будь-якого орієнтованого шляху ГНС довжини ребер не збільшуються.
2. У ГНС можливі цикли лише довжини 2 і кожна слабко зв'язна компонента ГДС із 2 і більше вершинами має рівно один 2-цикл.
3. Для точок площини ГНС є планарним графом зі степенями вершин, що не перевищують 6. Якщо точки мають загальне положення, степінь вершин не перевищує 5.
4. ГНС (розглядається як неорієнтований граф з дозволом кількох найближчих сусідів) множини точок площини або будь-якого простору вищої розмірності є підграфом тріангуляції Делоне, графа Габріеля і ^[en]. Якщо точки мають загальне положення або якщо накладено умову єдиності найближчого сусіда, ГНС є лісом, підграфом евклідового мінімального кістякового дерева.

Примітки

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

Література

• Ф. Препарата, М. Шеймос. Вычислительная геометрия: Введение. — М. : «Мир», 1989. — УДК 681.3 513.
• D. Eppstein, M. S. Paterson, Frances Yao. On nearest-neighbor graphs // . — 1997. — Т. 17, вип. 3 (19 червня). — С. 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 (19 червня). — С. 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 // . — 2013. — С. 137–144. — DOI:10.1145/2462356.2462378.

Посилання

• C++ library for efficient nearest-neighbor graph construction Архівовано січень 23, 2021 на сайті Wayback Machine.