アートギャラリー問題の計算複雑性

我々は、Kleeによって最初に提起されたアートギャラリー問題とそのバリエーションの計算複雑性について研究します。具体的には、n壁の単純連結アートギャラリーを見ることができる頂点ガードの最小数を決定する問題がNP困難であることが示されます。この証明は、単純連結多角形領域における辺ガードの最小数および点ガードの最小数を決定する問題もNP困難であることを示すように修正できます。副産物として、単純多角形をその合併が元の多角形となる最小数の星形多角形に分解する問題もNP困難であることが示されます。