M. Eskandari^{1}, P. Hadi^{2} ^{1,2}Faculty of Mathematical Sciences
Alzahra University
Tehran, IRAN

Abstract. Guarding of an environment by cameras or guards is a longstanding problem in computational geometry. In this paper, we introduce a new type of guarding problems called -guarding using staircase visibility. A point inside an orthogonal environment is said to be staircase visible for a given camera if there exists a staircase path from camera to the point so that it is completely contained in the environment. In this model, we place a small number of guards inside an orthogonal polygon so that each point of polygon is staircase visible through at least four directions. We present an algorithm for -guarding an arbitrary orthogonal polygon that yields an upper bound for the number of guards that protect an orthogonal polygon through four directions.

AMS Subject Classification: 68U05, 68R01

Key Words and Phrases: computational geometry, art gallery problem, visibility, -guarding