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

Граф відно сних о колів це неорієнтований граф визначений на множині точок на евклідовій площині з єднанням двох точок p

Граф відносних околів

Граф відносних околів

Граф відно́сних о́колів — це неорієнтований граф, визначений на множині точок на евклідовій площині з'єднанням двох точок p і q ребом тоді, коли не існує третьої точки r, яка ближче як до p, так і до q, ніж p і q одна до одної. Цей граф 1980 року запропонував [en] як спосіб визначення на множині точок структури, яка відбиває людське сприйняття форми множини.

image
Граф відносних околів 100 випадкових точок у одиничному квадраті.

Алгоритми

Суповіт показав, як ефективно побудувати граф відносних околів за час O(n log n). Граф можна обчислити за O (n) для довільної множини точок, рівномірно розподілених у одиничному квадраті. Граф відносних околів можна обчислити за лінійний час із тріангуляції Делоне множини точок.

Узагальнення

Оскільки граф визначений лише в термінах відстаней між точками, граф відносних околів можна визначити для множин точок у просторі будь-якої розмірності і для неевклідових метрик.

Пов'язані графи

Граф відносних околsв є прикладом заснованого на [en] бета-кістяка. Це підграф тріангуляції Делоне. У свою чергу, евклідове мінімальне кістякове дерево є його підграфом, звідки випливає, що це зв'язний граф.

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

Примітки

  1. Jaromczyk, Kowaluk, 1991, с. 181–191.
  2. Toussaint, 1980, с. 261–268.
  3. Jaromczyk, Toussaint, 1992, с. 1502–1517.
  4. Supowit, 1983.
  5. Supowit, 1983, с. 428–448.
  6. Katajainen, Nevalainen, Teuhola, 1987, с. 77–86.
  7. Jaromczyk, Kowaluk, 1987, с. 233–241.
  8. Lingas, 1994, с. 199–208.
  9. Agarwal, Matoušek, 1992, с. 58–65.
  10. O'Rourke, 1982, с. 189–192.
  11. Lee, 1985, с. 327–332.
  12. Urquhart, 1980, с. 556–557.
  13. Toussaint, 1980, с. 860.
  14. Andrade, de Figueiredo, 2001.

Література

  • Toussaint G. T. The relative neighborhood graph of a finite planar set // Pattern Recognition. — 1980. — Т. 12, вип. 4. — С. 261–268. — DOI:10.1016/0031-3203(80)90066-7.
  • Jaromczyk J.W., Toussaint G.T. Relative neighborhood graphs and their relatives // Proceedings of the IEEE. — 1992. — Т. 80, вип. 9. — С. 1502–1517. — DOI:10.1109/5.163414.
  • Supowit K. J. The relative neighborhood graph, with an application to minimum spanning trees // . — 1983. — Т. 30, вип. 3. — С. 428–448. — DOI:10.1145/2402.322386.
  • Jyrki Katajainen, Olli Nevalainen, Jukka Teuhola. A linear expected-time algorithm for computing planar relative neighbourhood graphs // Information Processing Letters. — 1987. — Т. 25, вип. 2. — С. 77–86. — DOI:10.1016/0020-0190(87)90225-0.
  • Jaromczyk J. W., Kowaluk M. A note on relative neighborhood graphs // Proc. 3rd Symp. Computational Geometry. — New York, NY, USA : ACM, 1987. — С. 233–241. — DOI:10.1145/41958.41983.
  • Lingas A. A linear-time construction of the relative neighborhood graph from the Delaunay triangulation // Computational Geometry. — 1994. — Т. 4, вип. 4. — С. 199–208. — DOI:10.1016/0925-7721(94)90018-3.
  • Jaromczyk J. W., Kowaluk M. Constructing the relative neighborhood graph in 3-dimensional Euclidean space // Discrete Appl. Math.. — 1991. — Т. 31, вип. 2. — С. 181–191. — DOI:10.1016/0166-218X(91)90069-9.
  • Pankaj K. Agarwal, Jiří Matoušek. Relative neighborhood graphs in three dimensions // Proc. 3rd ACM–SIAM Symp. Discrete Algorithms. — 1992. — С. 58–65.
  • O'Rourke J. Computing the relative neighborhood graph in the L1 and L∞ metrics // Pattern Recognition. — 1982. — Т. 15, вип. 3. — С. 189–192. — DOI:10.1016/0031-3203(82)90070-X.
  • Lee D. T. Relative neighborhood graphs in the L1-metric // Pattern Recognition. — 1985. — Т. 18, вип. 5. — С. 327–332. — DOI:10.1016/0031-3203(85)90023-8.
  • 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.
  • Diogo Vieira Andrade, Luiz Henrique de Figueiredo. Good approximations for the relative neighbourhood graph // Proc. 13th Canadian Conference on Computational Geometry. — 2001.

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

Graf vidno snih o koliv ce neoriyentovanij graf viznachenij na mnozhini tochok na evklidovij ploshini z yednannyam dvoh tochok p i q rebom todi koli ne isnuye tretoyi tochki r yaka blizhche yak do p tak i do q nizh p i q odna do odnoyi Cej graf 1980 roku zaproponuvav en yak sposib viznachennya na mnozhini tochok strukturi yaka vidbivaye lyudske sprijnyattya formi mnozhini Graf vidnosnih okoliv 100 vipadkovih tochok u odinichnomu kvadrati AlgoritmiSupovit pokazav yak efektivno pobuduvati graf vidnosnih okoliv za chas O n log n Graf mozhna obchisliti za O n dlya dovilnoyi mnozhini tochok rivnomirno rozpodilenih u odinichnomu kvadrati Graf vidnosnih okoliv mozhna obchisliti za linijnij chas iz triangulyaciyi Delone mnozhini tochok UzagalnennyaOskilki graf viznachenij lishe v terminah vidstanej mizh tochkami graf vidnosnih okoliv mozhna viznachiti dlya mnozhin tochok u prostori bud yakoyi rozmirnosti i dlya neevklidovih metrik Pov yazani grafiGraf vidnosnih okolsv ye prikladom zasnovanogo na en beta kistyaka Ce pidgraf triangulyaciyi Delone U svoyu chergu evklidove minimalne kistyakove derevo ye jogo pidgrafom zvidki viplivaye sho ce zv yaznij graf Graf Urkgarta utvorenij vidalennyam najdovshogo rebra z kozhnogo trikutnika v triangulyaciyi Delone spochatku zaproponovano yak shvidkij metod obchislennya grafa vidnosnih okoliv Hocha graf Urkharta inodi vidriznyayetsya vid grafa vidnosnih okoliv jogo mozhna vikoristati yak aproksimaciyu grafa vidnosnih okoliv PrimitkiJaromczyk Kowaluk 1991 s 181 191 Toussaint 1980 s 261 268 Jaromczyk Toussaint 1992 s 1502 1517 Supowit 1983 Supowit 1983 s 428 448 Katajainen Nevalainen Teuhola 1987 s 77 86 Jaromczyk Kowaluk 1987 s 233 241 Lingas 1994 s 199 208 Agarwal Matousek 1992 s 58 65 O Rourke 1982 s 189 192 Lee 1985 s 327 332 Urquhart 1980 s 556 557 Toussaint 1980 s 860 Andrade de Figueiredo 2001 LiteraturaToussaint G T The relative neighborhood graph of a finite planar set Pattern Recognition 1980 T 12 vip 4 S 261 268 DOI 10 1016 0031 3203 80 90066 7 Jaromczyk J W Toussaint G T Relative neighborhood graphs and their relatives Proceedings of the IEEE 1992 T 80 vip 9 S 1502 1517 DOI 10 1109 5 163414 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 Jyrki Katajainen Olli Nevalainen Jukka Teuhola A linear expected time algorithm for computing planar relative neighbourhood graphs Information Processing Letters 1987 T 25 vip 2 S 77 86 DOI 10 1016 0020 0190 87 90225 0 Jaromczyk J W Kowaluk M A note on relative neighborhood graphs Proc 3rd Symp Computational Geometry New York NY USA ACM 1987 S 233 241 DOI 10 1145 41958 41983 Lingas A A linear time construction of the relative neighborhood graph from the Delaunay triangulation Computational Geometry 1994 T 4 vip 4 S 199 208 DOI 10 1016 0925 7721 94 90018 3 Jaromczyk J W Kowaluk M Constructing the relative neighborhood graph in 3 dimensional Euclidean space Discrete Appl Math 1991 T 31 vip 2 S 181 191 DOI 10 1016 0166 218X 91 90069 9 Pankaj K Agarwal Jiri Matousek Relative neighborhood graphs in three dimensions Proc 3rd ACM SIAM Symp Discrete Algorithms 1992 S 58 65 O Rourke J Computing the relative neighborhood graph in the L1 and L metrics Pattern Recognition 1982 T 15 vip 3 S 189 192 DOI 10 1016 0031 3203 82 90070 X Lee D T Relative neighborhood graphs in the L1 metric Pattern Recognition 1985 T 18 vip 5 S 327 332 DOI 10 1016 0031 3203 85 90023 8 Urquhart 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 Diogo Vieira Andrade Luiz Henrique de Figueiredo Good approximations for the relative neighbourhood graph Proc 13th Canadian Conference on Computational Geometry 2001

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