Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Граф Уркгарта множини точок на площині названий на честь Родеріка Б Уркгарта отримують видаленням найдовшої сторони з ко

Граф Уркгарта

Граф Уркгарта

Граф Уркгарта множини точок на площині, названий на честь Родеріка Б. Уркгарта, отримують видаленням найдовшої сторони з кожного трикутника в тріангуляції Делоне.

image
Приклад графа Уркгарта. З кожного трикутника Делоне видалено найдовші сторони (тонкі блакитні лінії).

Опис

Граф описав Уркгарт, який припустив, що видалення найдовшої сторони з кожного трикутника Делоне було б швидким способом побудови графа відносних околів (граф, що з'єднує пари точок p і q, якщо не існує третьої точки r, яка ближча до p і q, ніж до решти). Оскільки тріангуляцію Делоне можна побудувати за час image, така сама межа існує для графа Уркгарта. Хоча пізніше показано, що граф Уркгарта не точно те саме, що граф відносних околів, його можна використати як хороше наближення до цього графа. Задачу побудови графів відносних околів за час image, що стала відкритою після виявлення невідповідності між графом Уркгарта і графом відносних околів, розв'язав Суповіт.

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

Примітки

  1. Urquhart, 1980.
  2. Urquhart, 1980, с. 556–557.
  3. Toussaint, 1980, с. 860.
  4. Andrade, de Figueiredo, 2001.
  5. Supowit, 1983.
  6. Supowit, 1983, с. 428–448.

Література

  • Urquhart R. B. Algorithms for computation of relative neighborhood graph // Electronics Letters. — 1980. — Т. 16, вип. 14. — С. 556–557. — DOI:10.1049/el:19800386.
  • Toussaint G. T. Comment: Algorithms for computing relative neighborhood graph // Electronics Letters. — 1980. — Т. 16, вип. 22. — С. 860. — DOI:10.1049/el:19800611.. Ответ Уркхарта, DOI:10.1049/el:19800612 стр. 860—861.
  • Diogo Vieira Andrade, Luiz Henrique de Figueiredo. Good approximations for the relative neighbourhood graph // Proc. 13th Canadian Conference on Computational Geometry. — 2001.
  • Supowit K. J. The relative neighborhood graph, with an application to minimum spanning trees // . — 1983. — Т. 30, вип. 3. — С. 428–448. — DOI:10.1145/2402.322386.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Graf Urkgarta mnozhini tochok na ploshini nazvanij na chest Roderika B Urkgarta otrimuyut vidalennyam najdovshoyi storoni z kozhnogo trikutnika v triangulyaciyi Delone Priklad grafa Urkgarta Z kozhnogo trikutnika Delone vidaleno najdovshi storoni tonki blakitni liniyi OpisGraf opisav Urkgart yakij pripustiv sho vidalennya najdovshoyi storoni z kozhnogo trikutnika Delone bulo b shvidkim sposobom pobudovi grafa vidnosnih okoliv graf sho z yednuye pari tochok p i q yaksho ne isnuye tretoyi tochki r yaka blizhcha do p i q nizh do reshti Oskilki triangulyaciyu Delone mozhna pobuduvati za chas O n log n displaystyle O n log n taka sama mezha isnuye dlya grafa Urkgarta Hocha piznishe pokazano sho graf Urkgarta ne tochno te same sho graf vidnosnih okoliv jogo mozhna vikoristati yak horoshe nablizhennya do cogo grafa Zadachu pobudovi grafiv vidnosnih okoliv za chas O n log n displaystyle O n log n sho stala vidkritoyu pislya viyavlennya nevidpovidnosti mizh grafom Urkgarta i grafom vidnosnih okoliv rozv yazav Supovit Podibno do grafiv vidnosnih okoliv graf Urkgarta mnozhini tochok u zagalnomu polozhenni mistit evklidove minimalne kistyakove derevo cih tochok zvidki viplivaye sho cej graf zv yaznij PrimitkiUrquhart 1980 Urquhart 1980 s 556 557 Toussaint 1980 s 860 Andrade de Figueiredo 2001 Supowit 1983 Supowit 1983 s 428 448 LiteraturaUrquhart R B Algorithms for computation of relative neighborhood graph Electronics Letters 1980 T 16 vip 14 S 556 557 DOI 10 1049 el 19800386 Toussaint G T Comment Algorithms for computing relative neighborhood graph Electronics Letters 1980 T 16 vip 22 S 860 DOI 10 1049 el 19800611 Otvet Urkharta DOI 10 1049 el 19800612 str 860 861 Diogo Vieira Andrade Luiz Henrique de Figueiredo Good approximations for the relative neighbourhood graph Proc 13th Canadian Conference on Computational Geometry 2001 Supowit K J The relative neighborhood graph with an application to minimum spanning trees 1983 T 30 vip 3 S 428 448 DOI 10 1145 2402 322386

Дата публікації:
Топ