Låt P vara en ortogonal polygon med n hörn. En skjutkamera färdas fram och tillbaka längs ett ortogonalt linjesegment som motsvarar dess bana. Kameran ser en punkt p P om det finns en punkt q. s sådan att pq är en linje segment normalt till s som är helt innesluten i P. I MinimumCardinality Sliding Cameras (MCSC) problem, är målet att hitta en uppsättning S av glidande kameror av minimal kardinalitet att vakta P (dvs, varje punkt i P kan ses av några skjutkamera i S), medan i Minimum-Length Sliding Cameras (MLSC) problemet är målet att hitta en sådan uppsättning S för att minimera den totala längden på trajectories längs vilken kamerorna i S resa. I detta dokument besvarar vi frågor från Katz och Morgenstern (2011) genom att presentera följande resultat: (i) MLSC-problemet är polynomiskt dragbart även för ortogonala polygoner med hål, (ii) MCSC-problemet är NP-komplett när P tillåts ha hål, och (iii) en O(n 3 log n)-tid 2-ungelingalgoritm för MCSC-problemet på [NE]-star-formade ortogonala polygoner med n hörn (liknande, [NW]-, [SE]-, eller [SW]-star-formade ortogonala polygoner).
Målet i REF är att hitta det minsta antalet skjutkameror som kan ge mobil täckning, som kallas det minsta skjutkameraproblemet (MSC).
Guarding orthogonal art galleries with sliding cameras
{'venue': 'Comput. Geom.', 'journal': 'Comput. Geom.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}