Robni stražarji v trdnjavskem problemu

delo diplomskega seminarja

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2019
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[P. Berlič]
UDK:	519.1
COBISS:	18815833
Št. ogledov:	939
Št. prenosov:	159
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Edge guards for the fortress problem
Sekundarni povzetek:	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.
Sekundarne ključne besede:	mathematics;art gallery problem;polygon;guards;edge;fortress;
Vrsta dela (COBISS):	Delo diplomskega seminarja/zaključno seminarsko delo/naloga
Študijski program:	0
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Strani:	25 str.
ID:	11270663