Robni stražarji v trdnjavskem problemu

delo diplomskega seminarja

Primož Berlič (Author), Riste Škrekovski (Mentor)

Abstract

V diplomskem seminarju bomo obravnavali trdnjavski problem z robnimi stražarji. Trdnjavski problem je problem, pri katerem je trdnjava predstavljena kot poligon v ravnini, stražarji pa so točke ali robovi v ravnini. Dokazali bomo, da je v splošni trdnjavi $\lceil n/3 \rceil$ robnih stražarjev včasih potrebnih in vedno dovolj, da zastražijo zunanjost trdnjave. Pri ortogonalni trdnjavi pa potrebujemo $\lfloor n/4 \rfloor + 1$ robnih stražarjev.

Keywords

matematika;problem umetnostne galerije;poligon;stražarji;rob;trdnjava;

Data

Language:	Slovenian
Year of publishing:	2019
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FMF - Faculty of Mathematics and Physics
Publisher:	[P. Berlič]
UDC:	519.1
COBISS:	18815833
Views:	939
Downloads:	159
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Edge guards for the fortress problem
Secondary abstract:	In this seminar we consider the fortress problem with edge guards. In the fortress problem the fortress is considered a polygon and guards are points or edges in a plane. We will prove that it is always possible to guard exterior of general fortress with $\lceil n/3 \rceil$ edge guards and exterior of orthogonal fortress with $\lfloor n/4 \rfloor + 1$ edge guards.
Secondary keywords:	mathematics;art gallery problem;polygon;guards;edge;fortress;
Type (COBISS):	Final seminar paper
Study programme:	0
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Pages:	25 str.
ID:	11270663