Hlídání galerie

Abstract

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

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