Граф Уркгарта множини точок на площині, названий на честь Родеріка Б. Уркгарта, отримують видаленням найдовшої сторони з кожного трикутника в тріангуляції Делоне.
Опис Граф описав Уркгарт, який припустив, що видалення найдовшої сторони з кожного трикутника Делоне було б швидким способом побудови графа відносних околів (граф, що з'єднує пари точок p і q, якщо не існує третьої точки r, яка ближча до p і q, ніж до решти). Оскільки тріангуляцію Делоне можна побудувати за час , така сама межа існує для графа Уркгарта. Хоча пізніше показано, що граф Уркгарта не точно те саме, що граф відносних околів, його можна використати як хороше наближення до цього графа. Задачу побудови графів відносних околів за час , що стала відкритою після виявлення невідповідності між графом Уркгарта і графом відносних околів, розв'язав Суповіт.
Подібно до графів відносних околів, граф Уркгарта множини точок у загальному положенні містить евклідове мінімальне кістякове дерево цих точок, звідки випливає, що цей граф зв'язний.
Примітки
Література
. Ответ Уркхарта, стр. 860—861.