戻る

美術館定理

頂点が n 個の多角形の部屋は、⌊n/3⌋ 人の監視員がいれば必ず全体を見張れる。⌊n/3⌋ 人より少ないと見張れない部屋もある。監視員を置いて見える範囲を調べ、三角形分割と 3 色のぬり分けによるフィスクの方法で配置を求める。

解説

美術館問題は、「美術館の中を、何人の監視員がいればすべて見張れるか」という問いで、計算幾何学の見え方（可視性）の問題である。

部屋を単純多角形、監視員を多角形の中の点とみなす。多角形の中のどの点 p にも、p と結んだ線分が多角形の外に出ない監視員 q がいるとき、監視員たちは多角形全体を見張っている。

1973 年、ヴィクター・クレー（Victor Klee）がこの問いをヴァーツラフ・フヴァータル（Václav Chvátal）に出した。

フヴァータルは 1975 年に、頂点が n 個の単純多角形を見張るには、⌊n/3⌋ 人の監視員で必ず足りること、そして ⌊n/3⌋ 人より少ないと見張れない多角形もあることを証明した。⌊x⌋ は x 以下で最大の整数を表す。

英語では Chvátal's art gallery theorem と呼ばれる。日本語版 Wikipedia には記事がないため、このツールでは「美術館定理」と訳した。

このツールの「くし形」は、歯が 5 本、頂点が 15 個の多角形である。1 人の監視員から 2 本の歯の先が同時に見えることはないので、5 ＝ ⌊15/3⌋ 人いる。

星形は頂点が 16 個で ⌊16/3⌋ ＝ 5 だが、まん中の 1 人で全体が見える。⌊n/3⌋ は、どんな多角形でも足りる人数であって、いつも必要な人数ではない。

1978 年、スティーブ・フィスク（Steve Fisk）は、3 色のぬり分けを使った短い証明を示した。

まず、頂点を増やさずに、対角線で多角形を三角形に分ける（三角形分割）。三角形は n − 2 個になる。

次に、どの三角形でも 3 つの頂点が別の色になるように、頂点を 3 色でぬり分ける。すると、どの三角形にも 3 色がそろうので、1 つの色の頂点すべてに監視員を置けば、どの三角形も見張れる。

3 色の頂点の数を合わせると n なので、いちばん少ない色の頂点は ⌊n/3⌋ 個以下になる。

この証明は、数学の名証明を集めた本『Proofs from THE BOOK』にも載っている。

頂点が 4 個以上の単純多角形には、少なくとも 2 つの「耳」がある。耳とは、2 辺が多角形の辺で、残りの 1 辺が多角形の内部にある三角形である。

このツールでは、耳を 1 つずつ切り取って三角形分割する（耳の切り取り法）。1 つ切り取ると頂点が 1 つ減り、最後に三角形が 1 つ残る。

ぬり分けは逆の順にたどる。残った三角形を 3 色でぬり、切り取った耳を逆の順にもどすと、耳の頂点の両どなりはもう色が決まっているので、残りの 1 色に決まる。

監視員から見える範囲（可視多角形）は、監視員から多角形の各頂点の向きと、そのわずかに左右の向きに光線を出し、いちばん近い辺に当たる点を角度の順に結んで求める。

見えている部分の面積は、すべての頂点と辺の交点の x 座標で図を縦の帯に分け、帯ごとに縦線で切った長さから正確に計算する。

辺がすべて直角に交わる多角形（直交多角形）では、⌊n/4⌋ 人で足りる。

監視員の数をいちばん少なくする置き方を求める問題は、監視員を頂点に限るものなど、多くの場合 NP 困難である。