M. Eskandari1, P. Hadi2 1,2Faculty of Mathematical Sciences
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
Download full article from here (pdf format).