Chvatalov teorem

master's thesis

• Title (english): Chvatal's theorem
• Author: Glorija Maloča
• Mentor: Slaven Kožić (mentor)
• Committee member: Slaven Kožić (predsjednik povjerenstva)
• Committee member: Sonja Štimac (član povjerenstva)
• Committee member: Vjekoslav Kovač (član povjerenstva)
• Committee member: Mea Bombardelli (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2022-07-14, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Problem čuvara umjetničke galerije sastoji se u određivanju najmanjeg broja čuvara potrebnih za nadzor galerije čiji tlocrt odgovara poligonu s \(n\) vrhova. Vaclav Chvatal prvi je dokazao da su \(\lfloor \frac{n}{3}\rfloor\) čuvara uvijek dovoljna za nadzor poligona s \(n\) vrhova. Glavni cilj ovog rada je temeljito proučiti ovaj rezultat, tj. Chvatalov teorem. U prvom dijelu rada izneseni su osnovni pojmovi i nekoliko zapažanja vezanih uz triangulaciju poligona koji su ključan dio Chvatalovog teorema. U nastavku je iznesen Chvatalov dokaz, a zatim i Fiskov dokaz istog rezultata koji se temelji na bojanju vrhova poligona. U drugom dijelu rada izdvojeno je nekoliko modifikacija izvornog problema te je dana detaljna analiza jedne posebne vrste poligona, ortogonalnih poligona. Potom je dokazano da za nadzor ortogonalnog poligona s \(n\) vrhova nikada neće zatrebati više od \(\lfloor \frac{n}{4}\rfloor\) stacionarnih čuvara. Na samom kraju, galerije su prenesene u tri dimenzije te su navedena osnovna zapažanja vezana uz čuvanje proizvoljnog poliedra.

Abstract (english)

The Art Gallery Problem consists of determining the minimum number of guards required to guard a gallery whose floor plan corresponds to a polygon with \(n\) vertices. Vaclav Chvatal was the first to prove that \(\lfloor \frac{n}{3}\rfloor\) guards will always be sufficient to guard a polygon with \(n\) vertices. The primary goal of this thesis is to thoroughly examine this result, i.e. Chvatal’s theorem. The first part of the thesis presents the fundamental concepts, results and several observations regarding polygon triangulation, which is a crucial part of Chvatal’s theorem. The text proceeds with Chvatal’s proof, followed by Fisk’s proof of the same result based on the coloring of the polygon vertices. In the second part of the thesis, several modifications of the original problem and a detailed analysis of a special type of polygon, the orthogonal polygon, are presented. A proof for the claim that guarding an orthogonal polygon with \(n\) vertices will never require more than \(\lfloor \frac{n}{4}\rfloor\) stationary guards is provided in the subsequent section. At the very end of the thesis, galleries in three-dimensional space are considered, and the essential observations related to guarding an arbitrary polyhedron are presented.

• Keywords: problem čuvara umjetničke galerije; broja čuvara; triangulacija poligona; Chvatalov dokaz; Fiskov dokaz; ortogonalni poligon
• Keywords (english): The Art Gallery Problem; number of guards; polygon triangulation; Chvatal’s proof; Fisk’s proof; orthogonal polygon
• Language: croatian
• URN:NBN: urn:nbn:hr:217:234678
• Study programme: Title: Mathematics and Computer Science Education; specializations in: Mathematics and Computer Science Education; Course: Mathematics and Computer Science Education; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra edukacije matematike i informatike (magistar/magistra edukacije matematike i informatike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2022-09-14 10:06:13