Computational complexity of art gallery problems
- 1 March 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 32 (2) , 276-282
- https://doi.org/10.1109/tit.1986.1057165
Abstract
We study the computational complexity of the art gallery problem originally posed by Klee, and its variations. Specifically, the problem of determining the minimum number of vertex guards that can see ann-wall simply connected art gallery is shown to be NP-hard. The proof can be modified to show that the problems of determining the minimum number of edge guards and the minimum number of point guards in a simply connected polygonal region are also NP-hard. As a byproduct, the problem of decomposing a simple polygon into a minimum number of star-shaped polygons such that their union is the original polygon is also shown to be NP-hard.Keywords
This publication has 11 references indexed in Scilit:
- Stationing guards in rectilinear art galleriesComputer Vision, Graphics, and Image Processing, 1984
- Galleries need fewer mobile guards: A variation on Chv tal's theoremGeometriae Dedicata, 1983
- Traditional Galleries Require Fewer WatchmenSIAM Journal on Algebraic Discrete Methods, 1983
- Some NP-hard polygon decomposition problemsIEEE Transactions on Information Theory, 1983
- An Optimal Algorithm for Determining the Visibility of a Polygon from an EdgeIEEE Transactions on Computers, 1981
- An efficient algorithm for decomposing a polygon into star-shaped polygonsPattern Recognition, 1981
- Decomposing a polygon into its convex partsPublished by Association for Computing Machinery (ACM) ,1979
- A short proof of Chvátal's Watchman TheoremJournal of Combinatorial Theory, Series B, 1978
- Decomposition of Polygons into Simpler Components: Feature Generation for Syntactic Pattern RecognitionIEEE Transactions on Computers, 1975
- A combinatorial theorem in plane geometryJournal of Combinatorial Theory, Series B, 1975