Computational Aspects of Problems on Visibility and Disk Graph Representations /
Dizertace se zaměřuje na dva koncepty široce studované v oblasti výpočetní geometrie. Jsou to viditelnostní grafy a grafy jednotkových disků. V oblasti viditelnosti jsme studovali bezkonfliktní barevné hlídání mnohoúhelníků, pro které jsme získali obecný algoritmus používající $O(n \log^2 n)$ bezkon...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2021
|
| Témata: | |
| On-line přístup: | https://is.muni.cz/th/en4va/ |
| LEADER | 05004ctm a22007217i 4500 | ||
|---|---|---|---|
| 001 | MUB01006489416 | ||
| 003 | CZ BrMU | ||
| 005 | 20240522140055.0 | ||
| 008 | 211006s2021 xr ||||| |||||||||||eng d | ||
| STA | |a POSLANO DO SKCR |b 2023-04-17 | ||
| 035 | |a (ISMU-VSKP)292433 | ||
| 040 | |a BOD114 |b cze |d BOD018 |e rda | ||
| 072 | 7 | |a 004.9 |x Speciální počítačové metody. Počítačová grafika |2 Konspekt |9 23 | |
| 072 | 7 | |a 514 |x Geometrie |2 Konspekt |9 13 | |
| 080 | |a 514:004 |2 MRF | ||
| 080 | |a 514 |2 MRF | ||
| 080 | |a 514.112.4 |2 MRF | ||
| 080 | |a 004.94 |2 MRF | ||
| 100 | 1 | |a Cagirici, Onur |% UČO 454907 |* [absolvent FI MU] |4 dis | |
| 242 | 1 | 0 | |a Computational Aspects of Problems on Visibility and Disk Graph Representations |y eng |
| 245 | 1 | 0 | |a Computational Aspects of Problems on Visibility and Disk Graph Representations / |c Onur Cagirici |
| 264 | 0 | |c 2021 | |
| 300 | |a 163 stran : |b ilustrace | ||
| 336 | |a text |b txt |2 rdacontent | ||
| 337 | |a bez média |b n |2 rdamedia | ||
| 338 | |a svazek |b nc |2 rdacarrier | ||
| 500 | |a Vedoucí práce: Petr Hliněný | ||
| 502 | |a Dizertace (Ph.D.)--Masarykova univerzita, Fakulta informatiky, 2021 | ||
| 520 | 2 | |a Dizertace se zaměřuje na dva koncepty široce studované v oblasti výpočetní geometrie. Jsou to viditelnostní grafy a grafy jednotkových disků. V oblasti viditelnosti jsme studovali bezkonfliktní barevné hlídání mnohoúhelníků, pro které jsme získali obecný algoritmus používající $O(n \log^2 n)$ bezkonfliktních barev, a normální barvení vrcholů ve viditelnostním grafu mnohoúhelníku, kde jsme získali algoritmus pro 4-barvení jednoduchého mnohoúhelníku. Mimo to jsme dokázali, že stejný problém barvení pro 5 barev je NP-úplný a že 4-barvení je už NP-úplné na viditelnostních grafech mnohoúhelníků s dírami. Poté jsme se posunuli k novému směru vnímání viditelnostních grafů, který uvažuje omezení reálného světa pro aplikace. Přesněji nedovoluje viditelnost na libovolnou vzdálenost, tedy dva velmi vzdálené objekty se nevidí, i když mezi nimi není fyzická překážka. Pro modelování tohoto omezení jsme zavedli jednotkově-diskové viditelnostní grafy a dokázali, že problém 3 barvení je pak už NP-úpln |% cze | |
| 520 | 2 | 9 | |a This thesis focuses on two concepts which are widely studied in the field of computational geometry. Namely, visibility and unit disk graphs. In the field of visibility, we have studied the conflict-free chromatic guarding of polygons, for which we have described a polynomial-time algorithm that uses $O(n \log^2 n)$ colors to guard a polygon in a conflict-free setting, and proper coloring of polygon visibility graphs, for which we have described an algorithm that returns a proper 4-coloring for a simple polygon. Besides, we have shown that the 5-colorability problem is NP-complete on visibility graphs of simple polygons, and 4-colorability is NP-complete on visibility graphs of polygons with holes. Then, we move further with the notion of visibility, and define a graph class which considers the real-world limitations for the applications of visibility graphs. That is, no physical object has infinite range, and two objects might not be mutually visible from a certain distance although |9 eng |
| 650 | 0 | 7 | |a výpočetní geometrie |7 ph184844 |2 czenas |
| 650 | 0 | 7 | |a geometrie |7 ph114624 |2 czenas |
| 650 | 0 | 7 | |a mnohoúhelníky |7 ph327599 |2 czenas |
| 650 | 0 | 7 | |a modelování a simulace |7 ph125543 |2 czenas |
| 650 | 0 | 9 | |a computational geometry |2 eczenas |
| 650 | 0 | 9 | |a polygons |2 eczenas |
| 650 | 0 | 9 | |a geometry |2 eczenas |
| 650 | 0 | 9 | |a modelling and simulation |2 eczenas |
| 655 | 7 | |a disertace |7 fd132024 |2 czenas | |
| 655 | 9 | |a dissertations |2 eczenas | |
| 658 | |a Informatika |b Fundamenty informatiky |c FI D-INF DIFI (DIFI) |2 CZ-BrMU | ||
| 700 | 1 | |a Hliněný, Petr, |d 1971- |7 mub2013777090 |% UČO 168881 |4 ths | |
| 710 | 2 | |a Masarykova univerzita. |b Katedra teorie programování |4 dgg | |
| 856 | 4 | 1 | |u https://is.muni.cz/th/en4va/ |
| CAT | |c 20211006 |l MUB01 |h 0422 | ||
| CAT | |a POSPEL |b 02 |c 20211010 |l MUB01 |h 2217 | ||
| CAT | |a POSPEL |b 02 |c 20211010 |l MUB01 |h 2218 | ||
| CAT | |a HANAV |b 02 |c 20211122 |l MUB01 |h 1503 | ||
| CAT | |a POSPEL |b 02 |c 20220629 |l MUB01 |h 0104 | ||
| CAT | |a POSPEL |b 02 |c 20221019 |l MUB01 |h 2326 | ||
| CAT | |a POSPEL |b 02 |c 20221101 |l MUB01 |h 0840 | ||
| CAT | |a VESELA |b 02 |c 20230109 |l MUB01 |h 1400 | ||
| CAT | |c 20230417 |l MUB01 |h 1117 | ||
| CAT | |a POSPEL |b 02 |c 20230629 |l MUB01 |h 0037 | ||
| CAT | |a POSPEL |b 02 |c 20240405 |l MUB01 |h 2124 | ||
| CAT | |a POSPEL |b 02 |c 20240408 |l MUB01 |h 1014 | ||
| CAT | |a VESELAX |b 02 |c 20240522 |l MUB01 |h 1400 | ||
| CAT | |a VESELAX |b 02 |c 20240522 |l MUB01 |h 1400 | ||
| CAT | |a POSPEL |b 02 |c 20241111 |l MUB01 |h 1100 | ||
| LOW | |a POSLANO DO SKCR |b 2023-04-17 | ||
| 994 | - | 1 | |l MUB01 |l MUB01 |m VYSPR |1 FI |a Fakulta informatiky |2 SKLAD |b sklad |3 Diz. práce 2021 |5 42005D2739 |8 20230109 |f 72 |f Týdenní |r 20230109 |
| AVA | |a INF50 |b FI |c sklad |d Diz. práce 2021 |e available |t K dispozici |f 1 |g 0 |h N |i 0 |j SKLAD | ||