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




Главная
Новости
Статьи
Ремонт
Каркасный дом
Несущие конструкции
Металлические конструкции
Прочность дорог
Дорожные материалы
Стальные конструкции
Воздухоопорные сооружения
Грунтовые основания




26.01.2021


26.01.2021


25.01.2021


24.01.2021


23.01.2021


21.01.2021


21.01.2021


20.01.2021


19.01.2021


19.01.2021





Яндекс.Метрика
         » » Граф Уркхарта

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

19.12.2020

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

Описание

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

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