Original title: Hlídání galerie
Translated title: Art gallery problem
Authors: Smolíková, Natálie ; Patáková, Zuzana (advisor) ; Žemlička, Jan (referee)
Document type: Bachelor's theses
Year: 2023
Language: cze
Abstract: [cze] [eng]
V 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
Keywords: art gallery|triangulation|orthogonal polygon|polygon|guards; galerie|triangulace|ortogonální polygon|polygon|strážci

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/182520

Permalink: http://www.nusl.cz/ntk/nusl-532043


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses