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

Пример графа Уркхарта — (тонкие голубые линии). Наиболее длинные рёбра удалены из каждого треугольника Делоне.

Граф Уркхарта множества точек на плоскости, названный в честь Родерика Б. Уркхарта, получается путём удаления самого длинного ребра из каждого треугольника в триангуляции Делоне.

Описание

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

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