www.wikidata.uk-ua.nina.az

Геометричний кістяк англ geometric spanner або t кістяковий граф або t кістяк спочатку введено як зважений граф на множи

Геометричний кістяк

Геометричний кістяк (англ. geometric spanner) або t-кістяковий граф, або t-кістяк спочатку введено як зважений граф на множині точок як вершин, для якого існує t-шлях між будь-якою парою вершин для фіксованого параметра t. t-шлях визначають як шлях у графі з вагою, що не перевищує в t разів просторову відстань між кінцевими точками. Параметр t називають коефіцієнтом розтягу[en] кістяка.

В обчислювальній геометрії концепцію першим обговорював Л. П. Чу (1986), хоча термін «spanner» (кістяк) у статті не згадано.

Поняття кістякового дерева відоме в теорії графів: t-кістяки — це кістякові підграфи графів зі схожими властивостями розтягування, де відстань між вершинами графа визначається в термінах теорії графів. Тому геометричні кістяки є кістяковими деревами повних графів, укладених у площину, в яких ваги ребер дорівнюють відстаням між вершинами у відповідній метриці.

Остовы можна використати в обчислювальній геометрії для розв'язання деяких задач на близькість[en]. Вони мають також застосування в інших галузях, таких як планування руху, в комунікаційних мережах — надійність мережі, оптимізація роумінгу в мобільних мережах тощо.

Різні кістяки та міри якості ред.

Для аналізу якості кістяків використовують різні міри. Найпоширенішими мірами є число ребер, загальна вага та найбільший степінь вершин. Асимптотично оптимальні значення для цих мір — ребер, для загальної ваги та для найбільшого степеня (тут MST означає вагу мінімального кістякового дерева).

Відомо, що пошук кістяка на евклідовій площині з найменшим розтягом на n точках з максимум m ребрами є NP-складною задачею.

Є багато алгоритмів, які добре поводяться за різних мір якості. Швидкі алгоритми включають кістякову цілком розділену декомпозицію пар[en] (ЦРДП) і тета-графи, які будують кістяки з лінійним числом ребер за час . Якщо потрібні кращі ваги і степені вершин, жадібний кістяк обчислюється майже за квадратичний час.

Тета-граф ред.

Тета-граф або -граф належить до сімейства кістяків, заснованих на конусі. Основний метод побудови полягає в поділі простору навколо кожної вершини на множину конусів (плоский конус - це два промені, тобто кут), які поділяють вершини графа, що залишилися. Подібно до графів Яо, -граф містить максимум по одному ребру для конуса. Підхід відрізняється способом вибору ребер. Тоді як у графах Яо вибирають найближчу вершину відповідно до метричної відстані у графі, у -графі визначають фіксований промінь, що міститься в кожному конусі (зазвичай бісектрису конуса) і вибирають найближчих сусідів (тобто з найменшою відстанню до променя).

Жадібний кістяк ред.

Жадібний кістяк або жадібний граф визначають як граф, отриманий багаторазовим додаванням ребра між точками, що не мають t-шляху. Алгоритми обчислення цього графа згадують як алгоритми жадібного кістяка. З побудови очевидно випливає, що жадібні графи є t-кістяками.

Жадібні кістяки відкрили 1989 року незалежно Альтхефер і Берн (не опубліковано).

Жадібний кістяк досягає асимптотично оптимального числа ребер, загальної ваги і найбільшого степеня вершини і дає кращі величини міри на практиці. Його можна побудувати за час з використанням простору .

Тріангуляція Делоне ред.

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

Найкраща верхня відома межа для тріангуляції Делоне дорівнює -кістяка для його вершин. Нижню межу збільшено від до 1,5846.

Цілком розділена декомпозиція пар ред.

Кістяк можна побудувати з цілком розділеної декомпозиції пар[en] у такий спосіб. Будуємо граф із набором точок як вершинами і для кожної пари в ЦРДП додаємо ребро з довільної точки до довільної точки . Зауважимо, що отриманий граф має лінійне число ребер, оскільки ЦРДП має лінійне число пар.

Згідно з доведенням, можна мати довільне значення для , виразивши із , що дає .

Див. також ред.

Примітки ред.

  1. Narasimhan, Smid, 2007.
  2. Chew, 1986, с. 169–177.
  3. Klein, Kutz, 2007, с. 196–207.
  4. Althöfer, Das, Dobkin, Joseph, Soares, 1993, с. 81–100.
  5. Bose, Carmi, Farshi, Maheshwari, Smid, 2010, с. 711–729.
  6. Keil, Gutwin, 1992, с. 13–28.
  7. Bose, Devroye, Loeffler, Snoeyink, Verma, 2009, с. 165–167.
  8. Callahan, Kosaraju, 1995, с. 67–90.

Література ред.

  • L. Paul Chew. There is a planar graph almost as good as the complete graph // Proc. 2nd Annual Symposium on Computational Geometry. — 1986. — DOI:10.1145/10515.10534.
  • Rolf Klein, Martin Kutz. Computing Geometric Minimum-Dilation Graphs is NP-Hard // Proc. 14th International Symposium in Graph Drawing, Karlsruhe, Germany, 2006 / Michael Kaufmann, Dorothea Wagner. — Springer Verlag, 2007. — Т. 4372. — (Lecture Notes in Computer Science) — ISBN 978-3-540-70903-9. — DOI:10.1007/978-3-540-70904-6.
  • Paul B. Callahan, S. Rao Kosaraju. Faster Algorithms for Some Geometric Graph Problems in Higher Dimensions // Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. — Austin, Texas, USA : Society for Industrial and Applied Mathematics, 1993. — (SODA '93) — ISBN 0-89871-313-7. — DOI:10.1145/313559.313777.
  • Althöfer I., Das G., Dobkin D. P., Joseph D., Soares J. On sparse spanners of weighted graphs. // Discrete & Computational Geometry. — 1993. — Т. 9 (31 жовтня). — DOI:10.1007/bf02189308.
  • Bose P., Carmi P., Farshi M., Maheshwari A., Smid. M. Computing the greedy spanner in near-quadratic time // Algorithmica. — 2010. — Т. 58 (31 жовтня). — DOI:10.1007/s00453-009-9293-4.
  • Keil J. M., Gutwin C. A. Classes of graphs which approximate the complete Euclidean graph // Discrete and Computational Geometry. — 1992. — Т. 7, вип. 1 (31 жовтня). — DOI:10.1007/BF02187821.
  • Prosenjit Bose, Luc Devroye, Maarten Loeffler, Jack Snoeyink, Vishal Verma. The spanning ratio of the Delaunay triangulation is greater than // Canadian Conference on Computational Geometry. — Vancouver, 2009.
  • Callahan P. B., Kosaraju S. R. A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields // Journal of the ACM. — 1995. — Т. 42, вип. 1 (January). — DOI:10.1145/200836.200853.
  • Giri Narasimhan, Michiel Smid. Geometric Spanner Networks. — Cambridge University Press, 2007. — ISBN 0-521-81513-4.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Geometrichnij kistyak angl geometric spanner abo t kistyakovij graf abo t kistyak spochatku vvedeno yak zvazhenij graf na mnozhini tochok yak vershin dlya yakogo isnuye t shlyah mizh bud yakoyu paroyu vershin dlya fiksovanogo parametra t t shlyah viznachayut yak shlyah u grafi z vagoyu sho ne perevishuye v t raziv prostorovu vidstan mizh kincevimi tochkami Parametr t nazivayut koeficiyentom roztyagu en kistyaka 1 V obchislyuvalnij geometriyi koncepciyu pershim obgovoryuvav L P Chu 1986 2 hocha termin spanner kistyak u statti ne zgadano Ponyattya kistyakovogo dereva vidome v teoriyi grafiv t kistyaki ce kistyakovi pidgrafi grafiv zi shozhimi vlastivostyami roztyaguvannya de vidstan mizh vershinami grafa viznachayetsya v terminah teoriyi grafiv Tomu geometrichni kistyaki ye kistyakovimi derevami povnih grafiv ukladenih u ploshinu v yakih vagi reber dorivnyuyut vidstanyam mizh vershinami u vidpovidnij metrici Ostovy mozhna vikoristati v obchislyuvalnij geometriyi dlya rozv yazannya deyakih zadach na blizkist en Voni mayut takozh zastosuvannya v inshih galuzyah takih yak planuvannya ruhu v komunikacijnih merezhah nadijnist merezhi optimizaciya roumingu v mobilnih merezhah tosho Zmist 1 Rizni kistyaki ta miri yakosti 2 Teta graf 3 Zhadibnij kistyak 4 Triangulyaciya Delone 5 Cilkom rozdilena dekompoziciya par 6 Div takozh 7 Primitki 8 LiteraturaRizni kistyaki ta miri yakosti red Dlya analizu yakosti kistyakiv vikoristovuyut rizni miri Najposhirenishimi mirami ye chislo reber zagalna vaga ta najbilshij stepin vershin Asimptotichno optimalni znachennya dlya cih mir O n displaystyle O n nbsp reber O M S T displaystyle O MST nbsp dlya zagalnoyi vagi ta O 1 displaystyle O 1 nbsp dlya najbilshogo stepenya tut MST oznachaye vagu minimalnogo kistyakovogo dereva Vidomo sho poshuk kistyaka na evklidovij ploshini z najmenshim roztyagom na n tochkah z maksimum m rebrami ye NP skladnoyu zadacheyu 3 Ye bagato algoritmiv yaki dobre povodyatsya za riznih mir yakosti Shvidki algoritmi vklyuchayut kistyakovu cilkom rozdilenu dekompoziciyu par en CRDP i teta grafi yaki buduyut kistyaki z linijnim chislom reber za chas O n log n displaystyle O n log n nbsp Yaksho potribni krashi vagi i stepeni vershin zhadibnij kistyak obchislyuyetsya majzhe za kvadratichnij chas Teta graf red Dokladnishe Teta grafTeta graf abo 8 displaystyle Theta nbsp graf nalezhit do simejstva kistyakiv zasnovanih na konusi Osnovnij metod pobudovi polyagaye v podili prostoru navkolo kozhnoyi vershini na mnozhinu konusiv ploskij konus ce dva promeni tobto kut yaki podilyayut vershini grafa sho zalishilisya Podibno do grafiv Yao 8 displaystyle Theta nbsp graf mistit maksimum po odnomu rebru dlya konusa Pidhid vidriznyayetsya sposobom viboru reber Todi yak u grafah Yao vibirayut najblizhchu vershinu vidpovidno do metrichnoyi vidstani u grafi u 8 displaystyle Theta nbsp grafi viznachayut fiksovanij promin sho mistitsya v kozhnomu konusi zazvichaj bisektrisu konusa i vibirayut najblizhchih susidiv tobto z najmenshoyu vidstannyu do promenya Zhadibnij kistyak red Zhadibnij kistyak abo zhadibnij graf viznachayut yak graf otrimanij bagatorazovim dodavannyam rebra mizh tochkami sho ne mayut t shlyahu Algoritmi obchislennya cogo grafa zgaduyut yak algoritmi zhadibnogo kistyaka Z pobudovi ochevidno viplivaye sho zhadibni grafi ye t kistyakami Zhadibni kistyaki vidkrili 1989 roku nezalezhno Althefer 4 i Bern ne opublikovano Zhadibnij kistyak dosyagaye asimptotichno optimalnogo chisla reber zagalnoyi vagi i najbilshogo stepenya vershini i daye krashi velichini miri na praktici Jogo mozhna pobuduvati za chas O n 2 log n displaystyle O n 2 log n nbsp z vikoristannyam prostoru O n 2 displaystyle O n 2 nbsp 5 Triangulyaciya Delone red Dokladnishe Triangulyaciya DeloneGolovnim rezultatom Chu bulo te sho dlya mnozhini tochok na ploshini isnuye triangulyaciya cih naboriv tochok taka sho dlya bud yakih dvoh tochok isnuye shlyah uzdovzh reber triangulyaciyi z dovzhinoyu sho ne perevishuye 1 0 displaystyle sqrt 1 0 nbsp evklidovoyi vidstani mizh dvoma tochkami Rezultat vikoristano v planuvanni ruhu dlya poshuku prijnyatnogo nablizhennya najkorotshogo shlyahu sered pereshkod Najkrasha verhnya vidoma mezha dlya triangulyaciyi Delone dorivnyuye 4 3 9 p 2 418 displaystyle 4 sqrt 3 9 pi approx 2 418 nbsp kistyaka dlya jogo vershin 6 Nizhnyu mezhu zbilsheno vid p 2 displaystyle scriptstyle pi 2 nbsp do 1 5846 7 Cilkom rozdilena dekompoziciya par red Kistyak mozhna pobuduvati z cilkom rozdilenoyi dekompoziciyi par en u takij sposib Buduyemo graf iz naborom tochok S displaystyle S nbsp yak vershinami i dlya kozhnoyi pari A B displaystyle A B nbsp v CRDP dodayemo rebro z dovilnoyi tochki a A displaystyle a in A nbsp do dovilnoyi tochki b B displaystyle b in B nbsp Zauvazhimo sho otrimanij graf maye linijne chislo reber oskilki CRDP maye linijne chislo par 8 Rozshiryuvanij vmistNam potribni ci dvi vlastivosti CRDP en Lema 1 Nehaj A B displaystyle A B nbsp cilkom rozdilena dekompoziciya par vidnosno s displaystyle s nbsp Nehaj p p A displaystyle p p in A nbsp i q B displaystyle q in B nbsp Todi p p 2 s p q displaystyle pp leqslant 2 s pq nbsp Lema 2 Nehaj A B displaystyle A B nbsp cilkom rozdilena dekompoziciya par vidnosno s displaystyle s nbsp Nehaj p p A displaystyle p p in A nbsp i q q B displaystyle q q in B nbsp Todi p q 1 4 s p q displaystyle p q leqslant 1 4 s pq nbsp Nehaj A B displaystyle A B nbsp cilkom rozdilena dekompoziciya par vidnosno s displaystyle s nbsp Nehaj a b displaystyle a b nbsp rebro sho z yednuye A displaystyle A nbsp z B displaystyle B nbsp Nehaj ye tochka p A displaystyle p in A nbsp i tochka q B displaystyle q in B nbsp Za viznachennyam CRDP dostatno pereviriti sho ye t displaystyle t nbsp kistyakovij shlyah abo korotshe t displaystyle t nbsp shlyah mizh p displaystyle p nbsp i q displaystyle q nbsp yakij poznachimo P p q displaystyle P pq nbsp Poznachimo dovzhinu shlyahu P p q displaystyle P pq nbsp cherez P p q displaystyle P pq nbsp Pripustimo sho ye t displaystyle t nbsp shlyah mizh bud yakoyu paroyu tochok iz vidstannyu menshoyu abo rivnoyu p q displaystyle pq nbsp i s gt 2 displaystyle s gt 2 nbsp Z nerivnosti trikutnika pripushen i faktu sho p a 2 s p q p a lt p q displaystyle pa leqslant 2 s pq Rightarrow pa lt pq nbsp i b q 2 s p q b q lt p q displaystyle bq leqslant 2 s pq Rightarrow bq lt pq nbsp za lemoyu 1 mayemo P p q t p a a b t b q displaystyle P pq leqslant t pa ab t bq nbsp Z lemi 1 i 2 otrimuyemo P p q t 2 s p q 1 4 s p q t 2 s p q t 4 s p q 1 4 s p q 4 t 4 s p q p q 4 t 1 s 1 p q displaystyle begin aligned P pq amp leqslant t 2 s pq 1 4 s pq t 2 s pq amp t 4 s pq 1 4 s pq amp left frac 4t 4 s right pq pq amp left frac 4 t 1 s 1 right pq end aligned nbsp Tak sho t 4 t 1 s 1 t 1 4 t 1 s s t 1 4 t 1 s t 1 4 t 1 0 s t s 4 t 4 0 t s 4 s 4 0 t s 4 s 4 t s 4 s 4 displaystyle begin aligned t amp frac 4 t 1 s 1 t 1 amp frac 4 t 1 s s t 1 amp 4 t 1 s t 1 4 t 1 amp 0 st s 4t 4 amp 0 t s 4 s 4 amp 0 t s 4 amp s 4 t amp frac s 4 s 4 end aligned nbsp Otzhe yaksho t s 4 s 4 displaystyle t s 4 s 4 nbsp i s gt 4 displaystyle s gt 4 nbsp to mayemo t displaystyle t nbsp kistyak dlya naboru tochok S displaystyle S nbsp Zgidno z dovedennyam mozhna mati dovilne znachennya dlya t displaystyle t nbsp virazivshi s displaystyle s nbsp iz t s 4 s 4 displaystyle t s 4 s 4 nbsp sho daye s 4 t 1 t 1 displaystyle s 4 t 1 t 1 nbsp Div takozh red Evklidove minimalne kistyakove derevoPrimitki red Narasimhan Smid 2007 Chew 1986 s 169 177 Klein Kutz 2007 s 196 207 Althofer Das Dobkin Joseph Soares 1993 s 81 100 Bose Carmi Farshi Maheshwari Smid 2010 s 711 729 Keil Gutwin 1992 s 13 28 Bose Devroye Loeffler Snoeyink Verma 2009 s 165 167 Callahan Kosaraju 1995 s 67 90 Literatura red L Paul Chew There is a planar graph almost as good as the complete graph Proc 2nd Annual Symposium on Computational Geometry 1986 DOI 10 1145 10515 10534 Rolf Klein Martin Kutz Computing Geometric Minimum Dilation Graphs is NP Hard Proc 14th International Symposium in Graph Drawing Karlsruhe Germany 2006 Michael Kaufmann Dorothea Wagner Springer Verlag 2007 T 4372 Lecture Notes in Computer Science ISBN 978 3 540 70903 9 DOI 10 1007 978 3 540 70904 6 Paul B Callahan S Rao Kosaraju Faster Algorithms for Some Geometric Graph Problems in Higher Dimensions Proceedings of the Fourth Annual ACM SIAM Symposium on Discrete Algorithms Austin Texas USA Society for Industrial and Applied Mathematics 1993 SODA 93 ISBN 0 89871 313 7 DOI 10 1145 313559 313777 Althofer I Das G Dobkin D P Joseph D Soares J On sparse spanners of weighted graphs Discrete amp Computational Geometry 1993 T 9 31 zhovtnya DOI 10 1007 bf02189308 Bose P Carmi P Farshi M Maheshwari A Smid M Computing the greedy spanner in near quadratic time Algorithmica 2010 T 58 31 zhovtnya DOI 10 1007 s00453 009 9293 4 Keil J M Gutwin C A Classes of graphs which approximate the complete Euclidean graph Discrete and Computational Geometry 1992 T 7 vip 1 31 zhovtnya DOI 10 1007 BF02187821 Prosenjit Bose Luc Devroye Maarten Loeffler Jack Snoeyink Vishal Verma The spanning ratio of the Delaunay triangulation is greater than p 2 displaystyle scriptstyle pi 2 nbsp Canadian Conference on Computational Geometry Vancouver 2009 Callahan P B Kosaraju S R A Decomposition of Multidimensional Point Sets with Applications to k Nearest Neighbors and n Body Potential Fields Journal of the ACM 1995 T 42 vip 1 January DOI 10 1145 200836 200853 Giri Narasimhan Michiel Smid Geometric Spanner Networks Cambridge University Press 2007 ISBN 0 521 81513 4 Otrimano z https uk wikipedia org w index php title Geometrichnij kistyak amp oldid 36172092