Граф ближайших соседей
Граф ближайших соседей ( 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/ д н 1 - 1/ д ) баллов. [3] A k -NNG можно аппроксимировать с помощью эффективного алгоритма с полнотой 90%, который быстрее, чем поиск методом грубой силы . на порядок [4]
Другой вариант — граф самых дальних соседей (FNG), в котором каждая точка соединена ребром с самой дальней от нее точкой, а не с ближайшей точкой.
NNG для точек на плоскости, а также в многомерных пространствах находят применение, например, при сжатии данных , планировании движения и определении местоположения объектов . В статистическом анализе алгоритм цепочки ближайших соседей, основанный на следующих путях в этом графе, может использоваться для быстрого поиска иерархических кластеров . Графы ближайших соседей также являются предметом вычислительной геометрии .
Этот метод можно использовать для создания графа на узлах с неизвестной связностью.
NNG для наборов точек
[ редактировать ]Одномерный случай
[ редактировать ]Для набора точек на линии ближайшим соседом точки является ее левый или правый (или оба) сосед, если они отсортированы вдоль линии. Следовательно, NNG представляет собой путь или лес из нескольких путей и может быть построен за время O ( n log n ) путем сортировки . Эта оценка асимптотически оптимальна для некоторых моделей вычислений , поскольку построенный ННГ дает ответ на проблему уникальности элемента : достаточно проверить, имеет ли ННГ ребро нулевой длины. [5]
Высшие измерения
[ редактировать ]Если не указано иное, предполагается, что NNG представляют собой орграфы с уникально определенными ближайшими соседями, как описано во введении.
- Вдоль любого направленного пути в NNG длины ребер не увеличиваются. [2]
- В NNG возможны только циклы длины 2, и каждая слабосвязная компонента NNG с хотя бы двумя вершинами имеет ровно один 2-цикл. [2]
- Для точек на плоскости NNG представляет собой плоский граф со степенью вершин не более 6. Если точки находятся в общем положении , степень не превышает 5. [2]
- NNG (рассматриваемый как неориентированный граф с несколькими разрешенными ближайшими соседями) набора точек на плоскости или в любом более высоком измерении является подграфом триангуляции Делоне , графа Габриэля и графа Полу-Яо . [6] Если точки находятся в общем положении или если наложено условие единственного ближайшего соседа, NNG является лесом , подграфом евклидова минимального остовного дерева .
Ссылки
[ редактировать ]- ^ Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия. Введение . Спрингер-Верлаг . ISBN 0-387-96131-3 . 1-е издание; 2-е издание, исправленное и дополненное, 1988 г.; Русский перевод, 1989.
- ^ Jump up to: а б с д Эппштейн, Д .; Патерсон, Массачусетс ; Яо, Фрэнсис (1997). «О графах ближайших соседей» . Дискретная и вычислительная геометрия . 17 (3): 263–282. дои : 10.1007/PL00009293 .
- ^ Миллер, Гэри Л .; Тэн, Шанхуа ; Терстон, Уильям ; Вавасис, Стивен А. (1997). «Сепараторы для сферических упаковок и графов ближайших соседей» . Журнал Ассоциации вычислительной техники . 44 (1): 1–29. дои : 10.1145/256292.256294 .
- ^ Донг, Вэй; Моисей, Чарикар; Ли, Кай (28 марта 2011 г.). «Эффективное построение графа k-ближайших соседей для общих мер сходства» . Материалы 20-й международной конференции по Всемирной паутине . Ассоциация вычислительной техники. стр. 577–586. дои : 10.1145/1963405.1963487 . ISBN 9781450306324 . S2CID 207186093 .
- ^ Аггарвал, Алок; Кипнис, Шломо (август 1988 г.). «Лекция № 10, 10 марта 1988 г.: Ближайшая пара». В Аггарвале Алок; Вейн, Джоэл (ред.). Вычислительная геометрия: конспект лекций для 18.409, весна 1988 г. Лаборатория компьютерных наук Массачусетского технологического института. Наблюдение 1, с. 2.
- ^ Рахмати, З.; Кинг, В .; Уайтсайдс, С. (2013). Кинетические структуры данных для всех ближайших соседей и ближайшей пары на плоскости . Материалы 29-го симпозиума ACM по вычислительной геометрии . стр. 137–144. дои : 10.1145/2462356.2462378 .