Key points are not available for this paper at this time.
我们研究了Klee最初提出的艺术画廊问题及其变体的计算复杂性。具体而言，确定能够看到n个墙壁的简单连通艺术画廊所需的最小顶点守卫数量的问题被证明是NP-hard。该证明可以修改以显示，在简单连通多边形区域中确定最小边界守卫和最小点守卫数量的问题也是NP-hard。作为副产品，将简单多边形分解为最小数量的星形多边形以使其并集为原始多边形的问题也被证明是NP-hard.
Lee等人（Sat，）研究了这个问题。