アートギャラリーの問題

美術館問題、あるいは美術館問題は、計算幾何学においてよく研究されている可視性問題です。これは、次のような現実世界の問題に由来しています。

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

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

アートギャラリー問題は、ロボット工学など、様々な分野に応用できます。ロボット工学では、人工知能（AI）が周囲の状況に応じて動作を実行する必要があります。また、画像編集、舞台照明の問題、自然災害警報のためのインフラ整備など にも応用されています。

2次元

このギャラリーを 4 人の警備員がカバーできます。

元の問題には、アートギャラリー問題とも呼ばれる様々なバリエーションがあります。ガードの対象範囲がポリゴンの周囲、あるいは頂点に限定されるバージョンもあれば、周囲のみ、あるいはその一部のみをガードするバージョンもあります。

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

フヴァータルのアートギャラリー定理

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

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

歴史

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

フィスクの短い証明

三角形多角形の頂点を3色に彩色する。青い頂点は3つのガードの集合を形成し、これはアートギャラリー定理によって保証される最小数である。しかし、この集合は最適ではない。同じ多角形は2つのガード（例えば左端の2つの青いガード）によってのみガードされる。

スティーブ・フィスクの証明は非常に短くて簡潔であるため^{[ 4 ]} 、 THE BOOKの証明に収録されました^{[ 5 ]}。 証明は以下のとおりです。

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

一般化

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

元のアートギャラリー定理には、他にも多くの一般化と特殊化があります。^{[ 7 ]}例えば、直交多角形、つまり辺/壁が直角に交わる多角形の場合、ガードのみが必要です。この結果には少なくとも3つの異なる証明があり、いずれも単純ではありません。カーン、クラウ、クライトマン、ルビウ、サックとトゥーサンです。^{[ 8 ] [ 9 ]}${\displaystyle \lfloor n/4\rfloor }$

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

計算の複雑さ

アートギャラリー問題の決定問題版では、入力として多角形と数値kが与えられ、その多角形をk以下のガードでガードできるかどうかを判定する必要があります。この問題は-完全であり、ガードを多角形の辺のみに制限するバージョンも同様です。^{[ 11 ]}さらに、ガードの位置を頂点のみに制限するなど、他の標準的なバリエーションのほとんどはNP困難です。^{[ 12 ]}${\displaystyle \exists \mathbb {R} }$

ガード数の最小値を求める近似アルゴリズムに関して、 Eidenbenz、Stamm、Widmayer (2001) は、問題がAPX 困難であることを証明した。これは、多項式時間近似アルゴリズムでは、ある固定定数よりも良い近似比は達成できない可能性が高いことを意味している。Ghosh (1987) は、入力ポリゴンを凸サブ領域に離散化してから問題をセットカバー問題に簡約することで、頂点ガード数の最小値に対して対数近似が達成できることを示した。Valtr (1998)が示したように、アート ギャラリー問題から導出されたセット システムはVC 次元が制限されており、近似比がポリゴン頂点数ではなく最適なガード数の対数であるε ネットに基づくセットカバー アルゴリズムを適用できる。 ^{[ 13 ]}制限のないガードの場合、ガードの位置の数は無限にある可能性があるので、問題はさらに困難になる。ただし、ガードが細かいグリッド上に配置されるように制限することで、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 et al. (2019)によって多項式時間近似スキームが提案された。

Couto、de Rezende、de Souza (2011)は、頂点ガードのための正確なアルゴリズムを提案しました 。著者らは、様々な種類の多角形を用いて広範な計算実験を行い、数千の頂点を持つインスタンスであっても、比較的短い計算時間で最適解が得られることを示しました。これらのインスタンスの入力データと最適解はダウンロード可能です。^{[ 14 ]}

三次元

中心からすべての頂点が見えない直交多面体^{[ 15 ]}

内部の点がどの頂点からも見えない多面体の例。右の図は、中心Oを通る、ABCDに平行な断面を示しています。

上記の多面体内部からの 360° 球面パノラマ。すべての頂点が黄色の面で隠れていることがわかります( 360° インタラクティブ パノラマとして表示)

博物館を三次元の多面体として表現した場合、各頂点に監視装置を配置しても、博物館全体が監視下に置かれるとは限りません。多面体の表面全体が監視されるとしても、多面体によっては内部に監視されていない点が存在する可能性があります。^{[ 16 ]}

アプリケーション

この定理には多くの応用例が見つかっている: ^{[ 4 ]}

• 美術館の展示室全体を照らすのに役立ちます。
• 移動ロボットの衝突防止に役立ちます。
• ステージ上の演者が常に明るく照らされることを保証できます。
• 都市部では、無線送信機、携帯電話トランシーバー、光または赤外線ベースの汚染検出器を完全にカバーするために使用できます。
• コンピューター ビジョンでは、シーン内の可視領域を識別するのに役立ちます。

参照

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

注記

1. 多角形三角形分割の 3 色彩色可能性を証明するために、三角形分割の弱い双対グラフ(三角形ごとに 1 つの頂点と、隣接する三角形のペアごとに 1 つの辺を持つ無向グラフ) が木であることを観察します。これは、双対グラフのどのサイクルも、多角形に穴がないという仮定に反して、多角形の穴の境界を形成するためです。三角形が 2 つ以上あるときはいつでも、双対グラフ (任意の木と同様に) には、1 つの辺のみに沿って他の三角形に隣接する三角形に対応する、1 つの隣接頂点が必要です。この三角形を削除して形成される小さな多角形は、数学的帰納法によって 3 色彩色され、この色彩色は削除された三角形の 1 つの追加の頂点に簡単に拡張できます。 ^{[ 6 ]}

参考文献

1. オルーク（1987）、1ページ。
2. Chvátal (1975) .
3. フィスク（1978年）。
4. 「ルーブル美術館強盗事件：50年前の数学の問題が美術館の安全を保っていた可能性？」 www.bbc.com 2025年10月30日。
5. アイグナー＆ツィーグラー（2018） .
6. オルーク（1987）、13ページ。
7. シャーマー (1992) ;ウルティア (2000)
8. Kahn, Klawe & Kleitman (1983) ; Lubiw (1985) ; Sack & Toussaint (1988) .
9. オルーク（1987年）、31–80頁。
10. オルーク（1987年）、146–154頁。
11. アブラハムセン、アダマシェク、ミルツォフ (2022)。
12. オルークとスポウィット (1983) ;リーとリン (1986)。
13. Brönnimann & Goodrich (1995) .
14. クート、デ・レゼンデ、デ・ソウザ (2011)。
15. エリック・リプカ、ミニマルアートギャラリーについてのメモ、2019
16. オルーク（1987）、255ページ。

出典

• アブラハムセン、ミッケル。アダマシェク、アンナ。ミルツォウ、ティルマン (2022)、「アート ギャラリーの問題は完全です」、Journal of the ACM、69 (1): A4:1–A4:70、arXiv : 1704.06969、doi : 10.1145/3486220、MR 4402363、S2CID 245059672${\displaystyle \exists {\mathbb {R}}}$   
• Aggarwal, A. (1984)、「アートギャラリー定理：そのバリエーション、応用、アルゴリズム的側面」、ジョンズホプキンス大学博士論文。
• アイグナー、マーティン、ツィーグラー、ギュンター・M.（2018）、「第40章 博物館の警備方法」、THE BOOK（第6版）からの校正、ベルリン：シュプリンガー、pp.  281– 283、doi：10.1007/978-3-662-57265-8、ISBN 978-3-662-57264-1、MR  3823190。
• Ashur, Stav; Filtser, Omrit; Katz, Matthew J.; Saban, Rachel (2019)、「地形のようなグラフ：弱可視ポリゴンと地形を保護するためのPTAS」、Bampis, Evripidis; Megow, Nicole (編)、『近似とオンラインアルゴリズム - 第17回国際ワークショップ』、WAOA 2019、ミュンヘン、ドイツ、2019年9月12日～13日、改訂選集、Lecture Notes in Computer Science、vol. 11926、ベルリン：Springer、pp.  1～ 17、doi：10.1007/978-3-030-39479-0_1、ISBN 978-3-030-39478-3、S2CID  210936577。
• Avis, D. ; Toussaint, GT (1981)、「多角形を星型多角形に分解するための効率的なアルゴリズム」（PDF）、パターン認識、13 (6): 395– 398、Bibcode : 1981PatRe..13..395A、doi : 10.1016/0031-3203(81)90002-9。
• Bhattacharya, Pritam; Ghosh, Subir Kumar; Pal, Sudebkumar (2017),頂点ガードを用いた単純なポリゴンのガードのための定数近似アルゴリズム, arXiv : 1712.05492
• Bhattacharya, Pritam; Ghosh, Subir Kumar; Roy, ​​Bodhayan (2017)、「弱可視性多角形のガードの近似可能性」、Discrete Applied Mathematics、228 : 109– 129、arXiv : 1409.4621、doi : 10.1016/j.dam.2016.12.015、MR  3662965、S2CID  9916523
• エドゥアール・ボンネット。 Miltzow、Tillmann (2017)、「アート ギャラリー問題の近似アルゴリズム」、Aronov、Boris。 Katz、Matthew J. (編)、第 33 回計算幾何学に関する国際シンポジウム、SoCG 2017、2017 年 7 月 4 ～ 7 日、オーストラリア、ブリスベン、LIPIcs、vol. 77、Schloss Dagstuhl - Leibniz-Zentrum für Informatik、pp. 20:1–20:15、arXiv : 1607.05527、doi : 10.4230/LIPIcs.SoCG.2017.20、MR  3685692、S2CID  1293138。
• Brönnimann, H.; Goodrich, MT (1995)、「有限VC次元におけるほぼ最適な集合被覆」、離散および計算幾何学、14 (1): 463– 479、doi : 10.1007/BF02570718。
• Chvátal, V. (1975)、「平面幾何学における組合せ定理」、組合せ理論ジャーナル、シリーズB、18 : 39–41、doi : 10.1016/0095-8956(75)90061-1。
• Couto, M.; de Rezende, P.; de Souza, C. (2011)「アートギャラリーにおける頂点ガードの最小化のための正確なアルゴリズム」、International Transactions in Operational Research、18 (4): 425– 448、doi : 10.1111/j.1475-3995.2011.00804.x。
• デ・レゼンデ、P.デ・ソウザ、C.コウト、M. Tozoni, D. (2011)、「頂点ガードによるアート ギャラリー問題」、アート ギャラリー問題プロジェクト、コンピュータ研究所。
• Deshpande, Ajay; Kim, Taejung; Demaine, Erik D .; Sarma, Sanjay E. (2007)、「アートギャラリー問題に対する擬似多項式時間O(logn)近似アルゴリズム」、Proc. Worksh. Algorithms and Data Structures、Lecture Notes in Computer Science、vol. 4619、Springer-Verlag、pp.  163– 174、doi : 10.1007/978-3-540-73951-7_15、hdl : 1721.1/36243、ISBN 978-3-540-73948-7、S2CID  9148459。
• Eidenbenz, S.; Stamm, C.; Widmayer, P. (2001)、「ポリゴンと地形のガードに関する近似不可能性の結果」（PDF）、Algorithmica、31 (1): 79– 113、doi : 10.1007/s00453-001-0040-8、S2CID  14532511 、 2003年6月24日時点のオリジナル（PDF）からアーカイブ。
• フィスク、S.（1978）「Chvátalのウォッチマン定理の簡潔な証明」、Journal of Combinatorial Theory、シリーズB、24（3）：374、doi：10.1016/0095-8956（78）90059-X。
• Ghosh, SK (1987)、「アートギャラリー問題に対する近似アルゴリズム」、カナダ情報処理学会大会講演論文集、pp.  429– 434。
• Kahn, J.; Klawe, M .; Kleitman, D. (1983)「伝統的なギャラリーでは監視員の数は少なくて済む」SIAM J. Algebr. Discrete Methods , 4 (2): 194– 206, doi : 10.1137/0604020。
• Kooshesh, AA; Moret, BME (1992)、「三角形状の単純多角形の頂点の3色化」、パターン認識、25 (4): 443、Bibcode : 1992PatRe..25..443K、doi : 10.1016/0031-3203(92)90093-X。
• Krohn, Erik A.; Nilsson, Bengt J. (2013)、「単調多角形と直線多角形の近似ガード」、Algorithmica、66 (3): 564– 594、doi : 10.1007/s00453-012-9653-3、hdl : 2043/ 11487 、MR  3044626、S2CID  1458082。
• Lee, DT ; Lin, AK (1986)、「アートギャラリー問題の計算複雑性」、IEEE Transactions on Information Theory、32 (2): 276– 282、doi : 10.1109/TIT.1986.1057165。
• Lubiw, A. (1985)、「多角形領域の凸四辺形への分解」、第1回ACM計算幾何学シンポジウム、pp.  97– 106、doi : 10.1145/323233.323247、ISBN 0-89791-163-6、S2CID  15752916。
• オルーク、ジョセフ（1987）、アートギャラリー定理とアルゴリズム、オックスフォード大学出版局、ISBN 0-19-503965-3。
• オルーク、ジョセフ; サポウィット、ケネス J. (1983)、「いくつかのNP困難な多角形分解問題」、IEEE Transactions on Information Theory、29 (2): 181– 190、doi : 10.1109/TIT.1983.1056648、MR  0712374。
• Sack, JR ; Toussaint, GT (1988)、「直線多角形におけるガード配置」、Toussaint, GT (編)、『Computational Morphology』、North-Holland、pp.  153– 176。
• シャーマー、トーマス（1992）、「美術館における最近の成果」（PDF）、IEEE紀要、80（9）：1384–139 ​​9、doi：10.1109/5.163407。
• Urrutia, Jorge (2000)、「美術館と照明の問題」、Sack, J.-R.; Urrutia, Jorge (編)、『計算幾何学ハンドブック』、North-Holland、pp.  973– 1027、doi : 10.1016/B978-044482537-7/50023-1、ISBN 978-0-444-82537-7。
• Valtr, P. (1998)、「点が小さな領域を見ることができないギャラリーの保護」、イスラエル数学ジャーナル、104 (1): 1– 16、doi : 10.1007/BF02897056。