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

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

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

Граф описав Уркгарт[1], який припустив, що видалення найдовшої сторони з кожного трикутника Делоне було б швидким способом побудови графа відносних околів (граф, що з'єднує пари точок p і q, якщо не існує третьої точки r, яка ближча до p і q, ніж до решти). Оскільки тріангуляцію Делоне можна побудувати за час , така сама межа існує для графа Уркгарта[2]. Хоча пізніше показано, що граф Уркгарта не точно те саме, що граф відносних околів[3], його можна використати як хороше наближення до цього графа[4]. Задачу побудови графів відносних околів за час , що стала відкритою після виявлення невідповідності між графом Уркгарта і графом відносних околів, розв'язав Суповіт[5][6].

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

Примітки

[ред. | ред. код]

Література

[ред. | ред. код]
  • 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.