Guarding art galleries
Sandi Cof · Repository of the University of Ljubljana (University of Ljubljana) · 2016
Obravnavamo 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.