請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38386
標題: Computational Complexity of Art Gallery Problems
作者: D.T.Lee
A.K.Lin
出版社: Information Theory, IEEE Transactions on (Volume:32 , Issue: 2 )
摘要: 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.
URI: http://hdl.handle.net/11455/38386
ISSN: 0018-9448
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。