Art gallery problem とは

アートギャラリーの問題や博物館の問題は、計算幾何学においてよく研究されている可視性の問題です。それは、全体のギャラリーを一緒に見ることができる最低限のガード数で、アートギャラリーをガードする現実の問題から生じています。この問題の幾何学的なバージョンでは、アートギャラリーのレイアウトは単純なポリゴンで表され、各ガードはポリゴンのポイントで表されます。ポリゴン内のすべての点 p {\displaystyle p} について、 p {\displaystyle p} q {\displaystyle q} の間の線分がポリゴンから離れることがないような q S {\displaystyle q\in S} がある場合、点の集合 S {\displaystyle S} はポリゴンをガードすると言われています。