Hlídání galerie
Art gallery problem
bakalářská práce (OBHÁJENO)
![Náhled dokumentu](/bitstream/handle/20.500.11956/182520/thumbnail.png?sequence=7&isAllowed=y)
Zobrazit/ otevřít
Trvalý odkaz
http://hdl.handle.net/20.500.11956/182520Identifikátory
SIS: 257513
Kolekce
- Kvalifikační práce [10925]
Autor
Vedoucí práce
Oponent práce
Žemlička, Jan
Fakulta / součást
Matematicko-fyzikální fakulta
Obor
Matematika pro informační technologie
Katedra / ústav / klinika
Katedra algebry
Datum obhajoby
21. 6. 2023
Nakladatel
Univerzita Karlova, Matematicko-fyzikální fakultaJazyk
Čeština
Známka
Výborně
Klíčová slova (česky)
galerie|triangulace|ortogonální polygon|polygon|strážciKlíčová slova (anglicky)
art gallery|triangulation|orthogonal polygon|polygon|guardsV této práci se budeme zabývat klasickým problémem z výpočetní geometrie, a to problémem hlídání galerie, též známého pod anglickým názvem The Art Gallery Problem. Hlídání galerie se zabývá otázkou, jaký je nejmenší počet strážců, aby dohromady viděli celý půdorys galerie o n vrcholech. Hlavním cílem práce je nastudovat důkazy, že stačí ⌊n 3 ⌋ strážců v případě obecného polygonu a že stačí ⌊n 4 ⌋ strážců v případě ortogonálního polygonu. Náš důkaz ortogonální verze je oprava důkazu od Jorgeho Urrutii. Taktéž se zaměříme na optimalitu výsledků a na umístění strážců. 1
In this thesis, we study a classical problem in computational geometry, the Art Gallery Problem. The Art Gallery Problem originates from the question of what is the minimum number of guards required to see the entire gallery. The main goal of this paper is to provide proofs that ⌊n 3 ⌋ guards are sufficient for a simple polygon, and that ⌊n 4 ⌋ guards are sufficient for an orthogonal polygon. Our proof of the orthogonal version is a correction of Jorge Urrutia's proof. We also study the optimality of the results and the placement of guards. 1