Hlídání galerie
| Thesis title in Czech: | Hlídání galerie |
|---|---|
| Thesis title in English: | Art gallery problem |
| Key words: | galerie|triangulace|ortogonální polygon|polygon|strážci |
| English key words: | art gallery|triangulation|orthogonal polygon|polygon|guards |
| Academic year of topic announcement: | 2022/2023 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | RNDr. Zuzana Patáková, Ph.D. |
| Author: | Bc. Natálie Smolíková - assigned and confirmed by the Study Dept. |
| Date of registration: | 19.03.2023 |
| Date of assignment: | 11.04.2023 |
| Confirmed by Study dept. on: | 21.04.2023 |
| Date and time of defence: | 21.06.2023 10:00 |
| Date of electronic submission: | 08.05.2023 |
| Date of submission of printed version: | 15.05.2023 |
| Date of proceeded defence: | 21.06.2023 |
| Opponents: | doc. Mgr. et Mgr. Jan Žemlička, Ph.D. |
| Guidelines |
| 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). |
| References |
| 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 |