Jump to content

Граф Уркарта

Пример графа Уркарта : самые длинные ребра (тонко-голубые) удаляются из каждого треугольника Делоне.

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

Граф Уркарта был описан Уркартом (1980) , который предположил, что удаление самого длинного ребра из каждого треугольника Делоне будет быстрым способом построения графа относительной окрестности (графа, соединяющего пары точек и когда не существует третьей точки это ближе к обоим и чем они друг другу). Поскольку триангуляции Делоне можно построить за время та же временная граница справедлива и для графа Уркарта. [1] Хотя позже было показано, что граф Уркарта не совсем то же самое, что граф относительной окрестности, [2] его можно использовать как хорошее приближение к нему. [3] Задача построения относительных графов окрестностей в время, оставшееся открытым из-за несоответствия между графом Уркарта и графом относительной окрестности, было решено Суповитом (1983) . [4]

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

  1. ^ Уркарт, РБ (1980), «Алгоритмы вычисления графа относительной окрестности», Electronics Letters , 16 (14): 556–557, Bibcode : 1980ElL....16..556U , doi : 10.1049/el:19800386 .
  2. ^ Туссен, GT (1980), «Комментарий: Алгоритмы вычисления графа относительной окрестности», Electronics Letters , 16 (22): 860, Bibcode : 1980ElL....16..860T , doi : 10.1049/el:19800611 . Ответ Уркарта, doi : 10.1049/el:19800612, стр. 860–861.
  3. ^ Андраде, Диого Виейра; де Фигейредо, Луис Энрике (2001), «Хорошие приближения для графа относительной окрестности», Proc. 13-я Канадская конференция по вычислительной геометрии (PDF) .
  4. ^ Суповит, К.Дж. (1983), «Граф относительной окрестности с применением к минимальным остовным деревьям», J. ACM , 30 (3): 428–448, doi : 10.1145/2402.322386 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: d8fc43393bc87dbf498c025e59f298f5__1711218060
URL1:https://arc.ask3.ru/arc/aa/d8/f5/d8fc43393bc87dbf498c025e59f298f5.html
Заголовок, (Title) документа по адресу, URL1:
Urquhart graph - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)