Граф относительного соседства - Relative neighborhood graph

Граф относительного соседства 100 случайных точек в единичном квадрате.

В вычислительная геометрия, то граф относительной окрестности (ГСЧ) является неориентированный граф определены на множестве точек в Евклидова плоскость соединяя две точки п и q ребром, если не существует третьей точки р это ближе к обоим п и q чем они друг к другу. Этот график был предложен Годфрид Туссен в 1980 году как способ определения структуры из набора точек, которые соответствовали бы человеческому восприятию формы набора.[1][2]

Алгоритмы

Суповит (1983) показал, как эффективно построить граф относительных окрестностей в O (п бревноп) время.[3] Его можно вычислить за O (п) ожидаемое время, для случайного набора точек распределены равномерно в единичный квадрат.[4] Граф относительных окрестностей можно вычислить в линейное время от Триангуляция Делоне набора точек.[5][6]

Обобщения

Поскольку он определяется только в терминах расстояний между точками, граф относительной окрестности может быть определен для наборов точек в любом измерение,[1][7][8] и для неевклидовых метрик.[1][5][9][10]

Связанные графики

Граф относительных окрестностей является примером линза -основан бета-скелет. Это подграф из Триангуляция Делоне. В свою очередь, Евклидово минимальное остовное дерево является его подграфом, из чего следует, что это связный граф.

В График уркарта, граф, образованный удалением самого длинного ребра из каждого треугольника в триангуляции Делоне, изначально был предложен как быстрый метод вычисления графа относительных окрестностей.[11] Хотя граф Уркарта иногда отличается от графа относительных окрестностей[12] его можно использовать как приближение к графу относительных окрестностей.[13]

Рекомендации

  1. ^ а б c Туссен, Г. Т. (1980), "Граф относительных окрестностей конечного плоского множества", Распознавание образов, 12 (4): 261–268, Дои:10.1016/0031-3203(80)90066-7.
  2. ^ Jaromczyk, J.W .; Туссен, Г. (1992), "Графы относительного соседства и их родственники", Труды IEEE, 80 (9): 1502–1517, Дои:10.1109/5.163414.
  3. ^ Суповит, К. Дж. (1983), «Граф относительных окрестностей с приложением к минимальным остовным деревьям», J. ACM, 30 (3): 428–448, Дои:10.1145/2402.322386.
  4. ^ Катаянен, Юрки; Невалайнен, Олли; Теухола, Юкка (1987), "Линейный алгоритм ожидаемого времени для вычисления плоских графов относительных окрестностей", Письма об обработке информации, 25 (2): 77–86, Дои:10.1016/0020-0190(87)90225-0.
  5. ^ а б Jaromczyk, J. W .; Ковалук, М. (1987), "Замечание о графах относительных окрестностей", Proc. 3-й симп. Вычислительная геометрия, Нью-Йорк, Нью-Йорк, США: ACM, стр. 233–241, Дои:10.1145/41958.41983.
  6. ^ Лингас, А. (1994), "Построение в линейное время графа относительных окрестностей на основе триангуляции Делоне", Вычислительная геометрия, 4 (4): 199–208, Дои:10.1016/0925-7721(94)90018-3.
  7. ^ Jaromczyk, J. W .; Ковалук, М. (1991), "Построение графа относительных окрестностей в 3-мерном евклидовом пространстве", Дискретное приложение Математика., 31 (2): 181–191, Дои:10.1016 / 0166-218X (91) 90069-9.
  8. ^ Агарвал, Панкадж К.; Матаушек, Иржи (1992), "Графы относительных окрестностей в трех измерениях", Proc. 3-й симпозиум ACM – SIAM. Дискретные алгоритмы, стр. 58–65.
  9. ^ О'Рурк, Дж. (1982), "Вычисление графа относительной окрестности в L1 и L∞ показатели ", Распознавание образов, 15 (3): 189–192, Дои:10.1016 / 0031-3203 (82) 90070-X.
  10. ^ Ли, Д. Т. (1985), "Графы относительных окрестностей в L1-метрический ", Распознавание образов, 18 (5): 327–332, Дои:10.1016/0031-3203(85)90023-8.
  11. ^ Уркхарт, Р. Б. (1980), "Алгоритмы для вычисления графа относительной окрестности", Письма об электронике, 16 (14): 556–557, Дои:10.1049 / эл: 19800386.
  12. ^ Туссен, Г. Т. (1980), "Комментарий: Алгоритмы для вычисления графа относительной окрестности", Письма об электронике, 16 (22): 860, Дои:10.1049 / эл: 19800611. Ответ Уркхарта, стр. 860–861.
  13. ^ Андраде, Диого Виейра; де Фигейредо, Луис Энрике (2001), "Хорошие приближения для графа относительных окрестностей", Proc. 13-я канадская конференция по вычислительной геометрии (PDF).