Граф относительной окрестности

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

Алгоритмы

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

Обобщения

Поскольку граф относительной окрестности определяется только через расстояния между точками, его можно определить для наборов точек в любом измерении. ^[1]^[7]^[8] и для неевклидовых метрик. ^[1]^[5]^[9]^[10] Вычисление графа относительной окрестности для многомерных наборов точек можно выполнить за время. $O(n^{2})$ .

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

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

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

Ссылки

^ Jump up to: ^а ^б ^с Туссен, GT (1980), «Граф относительной окрестности конечного плоского множества», Распознавание образов , 12 (4): 261–268, doi : 10.1016/0031-3203(80)90066-7 .
^ Яромчик, JW; Туссен, GT (1992), «Графы относительной окрестности и их родственники», Proceedings of the IEEE , 80 (9): 1502–1517, doi : 10.1109/5.163414 .
^ Суповит, К.Дж. (1983), «Граф относительной окрестности с применением к минимальным остовным деревьям», Журнал ACM , 30 (3): 428–448, doi : 10.1145/2402.322386 .
^ Можжевельник, Юрки; Невалайнен, Олли; Теухола, Юкка (1987), «Линейный алгоритм ожидаемого времени для вычисления плоских графов относительной окрестности», Information Processing Letters , 25 (2): 77–86, doi : 10.1016/0020-0190(87)90225-0 .
^ Jump up to: ^а ^б Яромчик, JW; Ковалюк, М. (1987), «Заметки о графах относительной окрестности», Proc. 3-й симп. Вычислительная геометрия , Нью-Йорк, штат Нью-Йорк, США: ACM, стр. 233–241, doi : 10.1145/41958.41983 .
^ Лингас, А. (1994), «Построение графа относительной окрестности за линейное время из триангуляции Делоне», Computational Geometry , 4 (4): 199–208, doi : 10.1016/0925-7721(94)90018-3 .
^ Яромчик, JW; Ковалюк, М. (1991), «Построение графа относительной окрестности в трехмерном евклидовом пространстве», Discrete Applied Mathematics , 31 (2): 181–191, doi : 10.1016/0166-218X(91)90069-9 .
^ Агарвал, Панкадж К .; Матаушек, Иржи (1992), "Относительные графы окрестностей в трех измерениях" , Proc. 3-й симпозиум ACM – SIAM. Дискретные алгоритмы , стр. 58–65 .
^ О'Рурк, Дж. (1982), "Вычисление графа относительной окрестности в $L_{1}$ и $L_{\infty }$ метрики», Распознавание образов , 15 (3): 189–192, doi : 10.1016/0031-3203(82)90070-X .
^ Ли, Д.Т. (1985), "Относительные графы окрестностей в $L_{1}$ -метрика", Распознавание образов , 18 (5): 327–332, doi : 10.1016/0031-3203(85)90023-8 .
^ Уркарт, РБ (1980), «Алгоритмы вычисления графа относительной окрестности», Electronics Letters , 16 (14): 556–557, doi : 10.1049/el:19800386 .
^ Туссен, GT (1980), «Комментарий: Алгоритмы вычисления графа относительной окрестности», Electronics Letters , 16 (22): 860, doi : 10.1049/el:19800611 . Ответ Уркарта, стр. 860–861 .
^ АНДРАДЕ, Диего Виейра; де Фигейредо, Луис Энрике (2001), «Хорошие приближения для графа относительной окрестности» (PDF) , Proc. 13-я Канадская конференция по вычислительной геометрии .

[t80-1] Jump up to: ^а ^б ^с Туссен, GT (1980), «Граф относительной окрестности конечного плоского множества», Распознавание образов , 12 (4): 261–268, doi : 10.1016/0031-3203(80)90066-7 .

[2] Яромчик, JW; Туссен, GT (1992), «Графы относительной окрестности и их родственники», Proceedings of the IEEE , 80 (9): 1502–1517, doi : 10.1109/5.163414 .

[3] Суповит, К.Дж. (1983), «Граф относительной окрестности с применением к минимальным остовным деревьям», Журнал ACM , 30 (3): 428–448, doi : 10.1145/2402.322386 .

[4] Можжевельник, Юрки; Невалайнен, Олли; Теухола, Юкка (1987), «Линейный алгоритм ожидаемого времени для вычисления плоских графов относительной окрестности», Information Processing Letters , 25 (2): 77–86, doi : 10.1016/0020-0190(87)90225-0 .

[jk87-5] Jump up to: ^а ^б Яромчик, JW; Ковалюк, М. (1987), «Заметки о графах относительной окрестности», Proc. 3-й симп. Вычислительная геометрия , Нью-Йорк, штат Нью-Йорк, США: ACM, стр. 233–241, doi : 10.1145/41958.41983 .

[6] Лингас, А. (1994), «Построение графа относительной окрестности за линейное время из триангуляции Делоне», Computational Geometry , 4 (4): 199–208, doi : 10.1016/0925-7721(94)90018-3 .

[7] Яромчик, JW; Ковалюк, М. (1991), «Построение графа относительной окрестности в трехмерном евклидовом пространстве», Discrete Applied Mathematics , 31 (2): 181–191, doi : 10.1016/0166-218X(91)90069-9 .

[8] Агарвал, Панкадж К .; Матаушек, Иржи (1992), "Относительные графы окрестностей в трех измерениях" , Proc. 3-й симпозиум ACM – SIAM. Дискретные алгоритмы , стр. 58–65 .

[9] О'Рурк, Дж. (1982), "Вычисление графа относительной окрестности в $L_{1}$ и $L_{\infty }$ метрики», Распознавание образов , 15 (3): 189–192, doi : 10.1016/0031-3203(82)90070-X .

[10] Ли, Д.Т. (1985), "Относительные графы окрестностей в $L_{1}$ -метрика", Распознавание образов , 18 (5): 327–332, doi : 10.1016/0031-3203(85)90023-8 .

[11] Уркарт, РБ (1980), «Алгоритмы вычисления графа относительной окрестности», Electronics Letters , 16 (14): 556–557, doi : 10.1049/el:19800386 .

[12] Туссен, GT (1980), «Комментарий: Алгоритмы вычисления графа относительной окрестности», Electronics Letters , 16 (22): 860, doi : 10.1049/el:19800611 . Ответ Уркарта, стр. 860–861 .

[13] АНДРАДЕ, Диего Виейра; де Фигейредо, Луис Энрике (2001), «Хорошие приближения для графа относительной окрестности» (PDF) , Proc. 13-я Канадская конференция по вычислительной геометрии .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]