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/ |
| Shrnutí: | 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 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 |
|---|---|
| Popis jednotky: | Vedoucí práce: Petr Hliněný |
| Fyzický popis: | 163 stran : ilustrace |