摘要: We study the computational complexity of art gallery problem originally posed by Klee, and its variations. Specifically, determining minimum number vertex guards that can see an n -wall simply connected is shown to be NP-hard. The proof modified show problems edge point in a polygonal region are also As byproduct, decomposing simple polygon into star-shaped polygons such their union original
springer.com
acm.org
sci-hub.se 参考文章(13)
Avis, Toussaint, An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge IEEE Transactions on Computers. ,vol. 30, pp. 910- 914 ,(1981) , 10.1109/TC.1981.1675729
Joseph O'Rourke, Galleries need fewer mobile guards: A variation on Chvátal's theorem Geometriae Dedicata. ,vol. 14, pp. 273- 283 ,(1983) , 10.1007/BF00146907
J. O'Rourke, K. Supowit, Some NP-hard polygon decomposition problems IEEE Transactions on Information Theory. ,vol. 29, pp. 181- 190 ,(1983) , 10.1109/TIT.1983.1056648
Bernard Chazelle, David Dobkin, Decomposing a polygon into its convex parts symposium on the theory of computing. pp. 38- 48 ,(1979) , 10.1145/800135.804396
D. Avis, G.T. Toussaint, An efficient algorithm for decomposing a polygon into star-shaped polygons Pattern Recognition. ,vol. 13, pp. 395- 398 ,(1981) , 10.1016/0031-3203(81)90002-9
J. Kahn, M. Klawe, D. Kleitman, Traditional Galleries Require Fewer Watchmen Siam Journal on Algebraic and Discrete Methods. ,vol. 4, pp. 194- 206 ,(1983) , 10.1137/0604020
Herbert Edelsbrunner, Joseph O'Rourke, Emmerich Welzl, Stationing guards in rectilinear art galleries Graphical Models \/graphical Models and Image Processing \/computer Vision, Graphics, and Image Processing. ,vol. 27, pp. 167- 176 ,(1984) , 10.1016/S0734-189X(84)80041-9
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Steve Fisk, A short proof of Chvátal's Watchman Theorem Journal of Combinatorial Theory, Series B. ,vol. 24, pp. 374- ,(1978) , 10.1016/0095-8956(78)90059-X
Joseph O'Rourke, An alternate proof of the rectilinear art gallery theorem Journal of Geometry. ,vol. 21, pp. 118- 130 ,(1983) , 10.1007/BF01918136