Граф Уркгарта
Граф Уркгарта множини точок на площині, названий на честь Родеріка Б. Уркгарта, отримують видаленням найдовшої сторони з кожного трикутника в тріангуляції Делоне.
Граф описав Уркгарт[1], який припустив, що видалення найдовшої сторони з кожного трикутника Делоне було б швидким способом побудови графа відносних околів (граф, що з'єднує пари точок p і q, якщо не існує третьої точки r, яка ближча до p і q, ніж до решти). Оскільки тріангуляцію Делоне можна побудувати за час , така сама межа існує для графа Уркгарта[2]. Хоча пізніше показано, що граф Уркгарта не точно те саме, що граф відносних околів[3], його можна використати як хороше наближення до цього графа[4]. Задачу побудови графів відносних околів за час , що стала відкритою після виявлення невідповідності між графом Уркгарта і графом відносних околів, розв'язав Суповіт[5][6].
Подібно до графів відносних околів, граф Уркгарта множини точок у загальному положенні містить евклідове мінімальне кістякове дерево цих точок, звідки випливає, що цей граф зв'язний.
- ↑ Urquhart, 1980.
- ↑ Urquhart, 1980, с. 556–557.
- ↑ Toussaint, 1980, с. 860.
- ↑ Andrade, de Figueiredo, 2001.
- ↑ Supowit, 1983.
- ↑ Supowit, 1983, с. 428–448.
- Urquhart R. B. Algorithms for computation of relative neighborhood graph // Electronics Letters. — 1980. — Т. 16, вип. 14. — С. 556–557. — DOI:.
- Toussaint G. T. Comment: Algorithms for computing relative neighborhood graph // Electronics Letters. — 1980. — Т. 16, вип. 22. — С. 860. — DOI:.. Ответ Уркхарта, 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:.