Robni stražarji v trdnjavskem problemu : delo diplomskega seminarja

Berlič, Primož (author), Š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.

• Language: Slovenian
• Keywords: poligon, stražar, rob, trdnjava
• Work type: Final seminar paper
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2019
• PID: 20.500.12556/RUL-112623
• UDC: 519.1
• COBISS.SI-ID: 18815833
• Publication date in RUL: 27.10.2019

Secondary language

• Language: English
• Title: Edge guards for the fortress problem

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.

• Keywords: polygon, guard, edge, fortress