Граф Уркхарта

Граф Уркхарта был описан Уркхартом[1], который предположил, что удаление самого длинного пути из каждого треугольника Делоне было бы быстрым способом построения графа относительных окрестностей (граф, соединяющий пары точек p и q, если не существует третьей точки r, которая ближе к p и q, чем ко всем остальным). Поскольку триангуляцию Делоне можно построить за время ${\displaystyle O(n\log n)}$, та же самая граница имеет место для графа Уркхарта[2]. Хотя позднее было показано, что граф Уркхарта не в точности то же самое, что граф относительных окрестностей[3], он может быть использован как хорошее приближение к этому графу[4]. Задача построения графов относительных окрестностей за время ${\displaystyle O(n\log n)}$, ставшая открытой после обнаружения несоответствия между графом Уркхарта и графом относительных окрестностей, была решена Суповитом[5][6].

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