GUARDING ORTHOGONAL ART GALLERIES WITH SLIDING CAMERAS
Authors:
- 1 April 2011
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 21 (02) , 241-250
Abstract
We study the problem of guarding an orthogonal art gallery with security cameras sliding back and forth along straight tracks. We show that if only vertical (alternatively, horizontal) tracks are allowed, then a solution minimizing the number of tracks can be found in polynomial time, and if both orientations are allowed, then a 2-approximation can be found in polynomial time for x-monotone galleries.Keywords
This publication has 8 references indexed in Scilit:
- POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEMInternational Journal of Computational Geometry & Applications, 2007
- On guarding the vertices of rectilinear domainsComputational Geometry, 2007
- The strong perfect graph theoremAnnals of Mathematics, 2006
- TERRAIN DECOMPOSITION AND LAYERED MANUFACTURINGInternational Journal of Computational Geometry & Applications, 2001
- Two NP‐Hard Art‐Gallery Problems for Ortho‐PolygonsMathematical Logic Quarterly, 1995
- On rectilinear link distanceComputational Geometry, 1991
- Polynomial Algorithms for Perfect Graphs1984
- Convexity and a certain propertyP mIsrael Journal of Mathematics, 1970