Граф Уркгарта

Граф Уркгарта множини точок на площині, названий на честь Родеріка Б. Уркгарта, отримують видаленням найдовшої сторони з кожного трикутника в тріангуляції Делоне.

Приклад графа Уркгарта. З кожного трикутника Делоне видалено найдовші сторони (тонкі блакитні лінії).

Опис

Граф описав Уркгарт, який припустив, що видалення найдовшої сторони з кожного трикутника Делоне було б швидким способом побудови графа відносних околів (граф, що з'єднує пари точок p і q, якщо не існує третьої точки r, яка ближча до p і q, ніж до решти). Оскільки тріангуляцію Делоне можна побудувати за час $O(n\log n)$, така сама межа існує для графа Уркгарта. Хоча пізніше показано, що граф Уркгарта не точно те саме, що граф відносних околів, його можна використати як хороше наближення до цього графа. Задачу побудови графів відносних околів за час $O(n\log n)$, що стала відкритою після виявлення невідповідності між графом Уркгарта і графом відносних околів, розв'язав Суповіт.

Подібно до графів відносних околів, граф Уркгарта множини точок у загальному положенні містить евклідове мінімальне кістякове дерево цих точок, звідки випливає, що цей граф зв'язний.

Література

• Urquhart R. B. Algorithms for computation of relative neighborhood graph // Electronics Letters. — 1980. — Т. 16, вип. 14. — С. 556–557. — DOI:10.1049/el:19800386.
• Toussaint G. T. Comment: Algorithms for computing relative neighborhood graph // Electronics Letters. — 1980. — Т. 16, вип. 22. — С. 860. — DOI:10.1049/el:19800611.. Ответ Уркхарта, DOI:10.1049/el:19800612 стр. 860—861.
• Diogo Vieira Andrade, Luiz Henrique de Figueiredo. Good approximations for the relative neighbourhood graph // Proc. 13th Canadian Conference on Computational Geometry. — 2001.
• Supowit K. J. The relative neighborhood graph, with an application to minimum spanning trees // J. ACM. — 1983. — Т. 30, вип. 3. — С. 428–448. — DOI:10.1145/2402.322386.