График уркарта - Urquhart graph

Пример График уркарта: самые длинные края (тонкие голубые) удаляются из каждого треугольника Делоне.

В вычислительная геометрия, то График уркарта набора точек на плоскости, названного в честь Родерика Б. Уркхарта, получается удалением самого длинного край с каждого треугольник в Триангуляция Делоне.

Граф Уркхарта был описан Уркхарт (1980), который предположил, что удаление самого длинного ребра из каждого треугольника Делоне было бы быстрым способом построения граф относительной окрестности (граф, соединяющий пары точек п и q когда не существует третьей точки р это ближе к обоим п и q чем они друг к другу). Поскольку триангуляции Делоне могут быть построены за время O (п бревноп) такая же временная граница верна и для графа Уркхарта.[1] Хотя позже было показано, что граф Уркхарта не совсем то же самое, что граф относительных окрестностей,[2] его можно использовать как хорошее приближение к нему.[3] Задача построения графов относительных окрестностей в O (п бревноп) время, оставшееся открытым из-за несоответствия между графом Уркарта и графом относительной окрестности, было решено с помощью Суповит (1983).[4]

Как и граф относительных окрестностей, граф Уркхарта множества точек в общая позиция содержит Евклидово минимальное остовное дерево точек, откуда следует, что это связный граф.

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

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