アートギャラリーの問題

アートギャラリー問題または博物館問題は、計算幾何学においてよく研究されている可視性の問題です。これは、次のような現実世界の問題に由来しています。

「美術館では、美術館全体を監視できる警備員の最小人数は何人ですか？」

この問題の幾何学的バージョンでは、美術館のレイアウトは単純な多角形で表現され、各ガードはその多角形内の点で表現されます。多角形内のすべての点について、と の間の線分が多角形から出ない 点が存在する場合、点の集合は多角形をガードしていると言われます。${\displaystyle S}$${\displaystyle p}$${\displaystyle q\in S}$${\displaystyle p}$${\displaystyle q}$

アートギャラリー問題は、ロボット工学など、さまざまな分野に適用できます。ロボット工学では、人工知能 (AI) が周囲の状況に応じて動作を実行する必要があります。この問題が適用されるその他の分野としては、画像編集、ステージの照明問題、自然災害の警告のためのインフラストラクチャの設置などがあります。

元の問題には、アート ギャラリー問題とも呼ばれるさまざまなバリエーションがあります。一部のバージョンでは、ガードは周囲または多角形の頂点に制限されます。また、周囲のみ、または周囲のサブセットのみをガードする必要があるバージョンもあります。

ガードが頂点上に配置され、頂点のみがガードされる必要があるバージョンを解決することは、ポリゴンの 可視性グラフ上の支配集合問題を解決することと同じです。

ヴァーツラフ・フヴァータルにちなんで名付けられたフヴァータルのアートギャラリー定理は、警備員の最小数の 上限を示します。それは次のように述べています。

「頂点を持つ単純なポリゴンを保護するには、ガードは常に十分であり、場合によっては必要です。」${\displaystyle n}$${\displaystyle \left\lfloor n/3\right\rfloor }$

頂点/監視人/警備員がいくつ必要かという問題は、1973年にヴィクトル・クレーによってChvátalに提起されました。 ^[1] Chvátalはその後すぐにそれを証明しました。^{[2] Chvátalの証明は後にスティーブ・フィスクによって}3色化の議論によって簡略化されました。^{[3] Chvátalはより幾何学的なアプローチを採用していますが、フィスクは}グラフ理論のよく知られた結果を使用しています。

スティーブ・フィスクの証明は非常に短くて簡潔であるため、 「Proofs from THE BOOK」に収録されることが決定した。^[4] 証明は以下のとおりである。

まず、ポリゴンが三角形に分割されます(余分な頂点を追加せずに)。これは、検証された特定の条件下で三角形分割の存在が証明されているため可能です。結果として得られる三角形分割グラフの頂点は 3 色になることがあります。[ ^a]明らかに、3 色分割では、すべての三角形に 3 色すべてが必要です。ポリゴンのすべての三角形はその色の頂点によってガードされているため、いずれかの色の頂点は有効なガード セットを形成します。3 色でポリゴンのn個の頂点が分割されるため、頂点の数が最も少ない色は、最大でガードを持つ有効なガード セットを定義します。 ${\displaystyle \lfloor n/3\rfloor }$

証明を説明するために、以下の多角形を考えます。最初のステップは、多角形を三角形に分割することです (図 1を参照)。次に、適切な-色付け (図 2 ) を適用し、 赤、 青、緑の頂点があることを確認します 。頂点が最も少ない色は青または赤であるため、多角形はガードで覆うことができます (図 3 )。多角形には 頂点があり、であるため、これはアート ギャラリー定理と一致します。 ${\displaystyle 3}$${\displaystyle 4}$${\displaystyle 4}$${\displaystyle 6}$${\displaystyle 4}$${\displaystyle 14}$${\displaystyle \left\lfloor {\frac {14}{3}}\right\rfloor =4}$

• 
  図1
• 
  図2
• 
  図3

コーナーのガードに対する制限が、ポリゴンの外部ではない任意のポイントのガードに緩和された場合でも、Chvátal の上限は有効なままです。

オリジナルのアートギャラリー定理には、他にも多くの一般化や特殊化があります。^[6]たとえば、辺や壁が直角に交わる直交多角形の場合、ガードのみが必要です。この結果には少なくとも 3 つの異なる証明があり、どれも単純ではありません。Kahn、Klawe、Kleitmanによる証明、 Lubiwによる証明、SackとToussaintによる証明です。^{[7] [8]}${\displaystyle \lfloor n/4\rfloor }$

関連する問題として、任意の多角形の外側を覆うのに必要な警備員の数を求めるものがある（「要塞問題」）。警備員が多角形の境界上に配置されている場合は、警備員が必要になる場合があり、常に十分であるが、警備員が多角形の外側のどこに配置されている場合でも、警備員が必要になる場合があり、常に十分である。^[9]言い換えれば、無限の外部を覆うことは有限の内部を覆うことよりも難しい。 ${\displaystyle \lceil n/2\rceil }$${\displaystyle \lceil n/3\rceil }$

アートギャラリー問題の決定問題バージョンでは、入力として多角形と数k の両方が与えられ、多角形をk個以下のガードでガードできるかどうかを判断しなければなりません。この問題は、ガードが多角形のエッジに制限されているバージョンと同様に、-完全です。[ ^10]さらに、他の標準的なバリエーションのほとんど（ガード位置を頂点に制限するなど）はNP 困難です。^[11]${\displaystyle \exists \mathbb {R} }$

ガード数の最小値を求める近似アルゴリズムに関しては、Eidenbenz、Stamm & Widmayer (2001) は、問題が APX 困難であることを証明しました。これは、多項式時間近似アルゴリズムでは、ある固定定数よりも優れた近似比は達成できない可能性が高いことを意味します。Ghosh (1987) は、入力ポリゴンを凸サブ領域に離散化し、問題をセットカバー問題に縮小することで、頂点ガード数の最小値に対して対数近似が達成できることを示しました。Valtr (1998) が示したように、アートギャラリー問題から導出されたセットシステムはVC 次元が制限されており、近似比がポリゴン頂点数ではなく最適なガード数の対数であるε-ネットに基づくセットカバーアルゴリズムを適用できます。 ^[12]制限のないガードの場合、ガードの位置の数は無限であるため、問題はさらに困難になります。しかし、ガードが細かいグリッド上に制限されることにより、Bonnet & Miltzow (2017) で示されているように、いくつかの軽い追加の仮定の下で、より複雑な対数近似アルゴリズムを導くことができます。しかし、 Chvátal の上限に一致する、最大で頂点ガードのセットを見つけるための効率的なアルゴリズムが知られています。David AvisとGodfried Toussaint (1981) は、分割統治アルゴリズムを使用して、これらのガードの配置が最悪の場合でもO(n log n) 時間 で計算される可能性があることを証明しました。Kooshesh & Moret (1992) は、Fisk の短い証明とBernard Chazelleの線形時間平面三角測量アルゴリズム を使用して、線形時間アルゴリズムを提供しました。 ${\displaystyle \left\lfloor n/3\right\rfloor }$

穴のない単純な多角形については、頂点ガードとエッジガードのための定数係数近似アルゴリズムの存在が Ghosh によって推測されました。Ghosh の推測は、単純な多角形の 2 つの特殊なサブクラス、つまり単調な多角形とエッジから弱く見える多角形の頂点ガードに対して最初に当てはまることが示されました。Krohn と Nilsson (2013) は、ガードセットのサイズが頂点ガードの最適数の最大 30 倍になるように、単調な多角形の頂点ガードセットを多項式時間で計算する近似アルゴリズムを提示しました。Bhattacharya、Ghosh、Roy (2017) は、ガードセットのサイズが頂点ガードの最適数の最大 6 倍になるように、エッジから弱く見える単純な多角形の頂点ガードセットを O(n ² ) 時間で計算する近似アルゴリズムを提示しました。その後、Bhattacharya、Ghosh、Pal (2017) は、頂点ガードとエッジガードを使用して一般的な単純多角形を保護する定数係数近似アルゴリズムを提示することで、この予想を完全に解決したと主張しました。エッジから弱く見える単純多角形のサブクラスの頂点ガードについては、Ashur ら (2019) によって多項式時間の近似スキームが提案されました。

頂点ガードのための正確なアルゴリズムは、Couto、de Rezende、de Souza (2011) によって提案されました。著者らは、いくつかのクラスのポリゴンで大規模な計算実験を行い、数千の頂点に関連付けられたインスタンスでも比較的短い計算時間で最適なソリューションが見つかることを示しました。これらのインスタンスの入力データと最適ソリューションはダウンロード可能です。^[13]

博物館が3次元の多面体として表現されている場合、各頂点に警備員を配置しても博物館全体が監視されているとは限りません。多面体の表面全体が監視されますが、多面体によっては内部に監視されていない点がある場合があります。^[15]

• 直線多角形を星型多角形で覆う
• 星型多角形。アート ギャラリー問題を 1 つのガードで解決できる多角形のクラスです。
• 照明の問題: 壁が鏡張りの場合、ガードは 1 つで十分でしょうか?