Граф Уркхарта множества точек на плоскости, названный в честь Родерика Б. Уркхарта, получается путём удаления самого длинного ребра из каждого треугольника в триангуляции Делоне.
Описание Граф Уркхарта был описан Уркхартом, который предположил, что удаление самого длинного ребра из каждого треугольника Делоне было бы быстрым способом построения графа относительных окрестностей (граф, соединяющий пары точек p и q, если не существует третьей точки r, которая ближе к p и q, чем ко всем остальным). Поскольку триангуляцию Делоне можно построить за время , та же самая граница имеет место для графа Уркхарта. Позднее выяснилось, что граф Уркхарта не совпадает с графом относительных окрестностей, но остаётся его близким приближением. Задача построения графов относительных окрестностей за время , ставшая открытой после обнаружения несоответствия между графом Уркхарта и графом относительных окрестностей, была решена Суповитом.
Подобно графам относительных окрестностей, граф Уркхарта множества точек в общем положении содержит евклидово минимальное остовное дерево этих точек, откуда следует, что этот граф связен.
Примечания
Литература
. Ответ Уркхарта, стр. 860–861.
Категория:Вычислительная геометрия Категория:Геометрические графы Категория:Графы, имеющие собственные названия