Граф Уркарта
В вычислительной геометрии граф Уркарта набора точек на плоскости, названный в честь Родерика Б. Уркарта, получается путем удаления самого длинного ребра из каждого треугольника в триангуляции Делоне .
Граф Уркарта был описан Уркартом (1980) , который предположил, что удаление самого длинного ребра из каждого треугольника Делоне будет быстрым способом построения графа относительной окрестности (графа, соединяющего пары точек и когда не существует третьей точки это ближе к обоим и чем они друг другу). Поскольку триангуляции Делоне можно построить за время та же временная граница справедлива и для графа Уркарта. [1] Хотя позже было показано, что граф Уркарта не совсем то же самое, что граф относительной окрестности, [2] его можно использовать как хорошее приближение к нему. [3] Задача построения относительных графов окрестностей в время, оставшееся открытым из-за несоответствия между графом Уркарта и графом относительной окрестности, было решено Суповитом (1983) . [4]
Как и граф относительной окрестности, граф Уркарта множества точек общего положения содержит евклидово минимальное остовное дерево своих точек, из которого следует, что он является связным графом .
Ссылки
[ редактировать ]- ^ Уркарт, РБ (1980), «Алгоритмы вычисления графа относительной окрестности», Electronics Letters , 16 (14): 556–557, Bibcode : 1980ElL....16..556U , doi : 10.1049/el:19800386 .
- ^ Туссен, GT (1980), «Комментарий: Алгоритмы вычисления графа относительной окрестности», Electronics Letters , 16 (22): 860, Bibcode : 1980ElL....16..860T , doi : 10.1049/el:19800611 . Ответ Уркарта, doi : 10.1049/el:19800612, стр. 860–861.
- ^ Андраде, Диого Виейра; де Фигейредо, Луис Энрике (2001), «Хорошие приближения для графа относительной окрестности», Proc. 13-я Канадская конференция по вычислительной геометрии (PDF) .
- ^ Суповит, К.Дж. (1983), «Граф относительной окрестности с применением к минимальным остовным деревьям», J. ACM , 30 (3): 428–448, doi : 10.1145/2402.322386 .