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

Граф найбли́жчих сусі́дів (ГНС) для множини 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-ГНС задовольняють умовам теореми про планарне розбиття — їх можна розбити на два підграфи з максимум ${\tfrac {n(d+1)}{d+2}}$ вершинами, видаливши $\mathrm {O} (k^{\tfrac {1}{d}}n^{1-{\tfrac {1}{d}}}$ ) точок^[3].

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

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

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

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

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

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

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

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

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

Примітки

↑ Препарата, Шеймос, 1989.
↑ ^а ^б ^в ^г 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 (26 грудня). — С. 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 (26 грудня). — С. 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.

[FOOTNOTEПрепарата,_Шеймос1989-1] Препарата, Шеймос, 1989.

[FOOTNOTEEppstein,_Paterson,_Yao1997263–282-2] а ^б ^в ^г Eppstein, Paterson, Yao, 1997, с. 263–282.

[FOOTNOTEMiller,_Teng,_Thurston,_Vavasis1997-3] Miller, Teng, Thurston, Vavasis, 1997.

[FOOTNOTERahmati,_King,_Whitesides2013137–144-4] Rahmati, King, Whitesides, 2013, с. 137–144.

[1]

[2]

[3]

[4]