Robni stražarji v trdnjavskem problemu : delo diplomskega seminarja

Berlič, Primož (avtor), Škrekovski, Riste (mentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: poligon, stražar, rob, trdnjava
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2019
• PID: 20.500.12556/RUL-112623
• UDK: 519.1
• COBISS.SI-ID: 18815833
• Datum objave v RUL: 27.10.2019

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Edge guards for the fortress problem

Izvleček

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.

• Ključne besede: polygon, guard, edge, fortress