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

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

Описание

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

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