Hlídání galerie
| Název práce v češtině: | Hlídání galerie |
|---|---|
| Název v anglickém jazyce: | Art gallery problem |
| Klíčová slova: | galerie|triangulace|ortogonální polygon|polygon|strážci |
| Klíčová slova anglicky: | art gallery|triangulation|orthogonal polygon|polygon|guards |
| Akademický rok vypsání: | 2022/2023 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra algebry (32-KA) |
| Vedoucí / školitel: | RNDr. Zuzana Patáková, Ph.D. |
| Řešitel: | Bc. Natálie Smolíková - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 19.03.2023 |
| Datum zadání: | 11.04.2023 |
| Datum potvrzení stud. oddělením: | 21.04.2023 |
| Datum a čas obhajoby: | 21.06.2023 10:00 |
| Datum odevzdání elektronické podoby: | 08.05.2023 |
| Datum odevzdání tištěné podoby: | 15.05.2023 |
| Datum proběhlé obhajoby: | 21.06.2023 |
| Oponenti: | doc. Mgr. et Mgr. Jan Žemlička, Ph.D. |
| Zásady pro vypracování |
| Art gallery problém se zabývá jednoduchou otázkou, jaký je nejmenší počet strážců, kteří dohromady uvidí celou galerii? Jde o klasický problém z výpočetní geometrie s praktickým využitím například v robotice.
V práci se omezíme na galerie s n stěnami, kde půdorys je mnohoúhelník. Ví se, že vždy stačí nejvýše n/3 strážců. V případě, že jsou všechny stěny navzájem ortogonální, lze počet strážců snížit na n/4. Cílem práce je oba tyto důkazy nastudovat a srozumitelně vysvětlit, včetně jejich optimality. Studentka se bude rovněž zabývat otázkou, jak moc situaci ovlivňuje omezení na rozmístění strážců (pouze ve vrcholech x na hranách x kdekoli). |
| Seznam odborné literatury |
| V. Chvátal: A combinatorial theorem in plane geometry, Journal of Combinatorial Theory, Series B, volume 18, 39-41, 1975
S. Fisk: A short proof of Chvátal’s watchman theorem, Journal of Combinatorial Theory, Series B, volume 24, page 374, 1978 J. Kahn, M. Klawe, D. Kleitman: Traditional galleries require fewer watchmen, SIAM J. Algebr. Discrete Methods, 4(2): 194–206, 1983 J. O'Rourke: Art Gallery Theorems and Algorithms, Oxford University Press, 1987 J. Urrutia: Sixth proof of the Orthogonal Art Gallery problem, Technical report TR-97-03, Department of Computer Science, University of Ottawa, 1997 |