Nadzor galerijCof, Sandi (Avtor) Cencelj, Matija (Mentor) Gabrovšek, Boštjan (Komentor) problem galerijeObravnavamo osnovni problem varovanja galerij, katerih tlorisi so enostavni poligoni z n oglišči, varnostnike pa postavljamo v oglišča. Preko primera poligona z n oglišči pokažemo, da obstaja poligon, ki za nadzor potrebuje floor(n / 3) varnostnikov. S triangulacijo poligona in 3-barvanjem podamo algoritem, ki nam najde postavitev varnostnikov pri kateri floor(n / 3) varnostnikov zadosti za nadzor celotne galerije. Obravnavamo tudi delitev poligona na y-monotone dele in njihovo triangulacijo. Delovanje algoritmov ponazorimo na primerih.20162016-09-06 02:16:53Diplomsko delo84830COBISS_ID: 11134793sl