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

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

Опис

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

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