Ｋnに対して同色の三角形が存在しないように配色することができるかという問題は，グラフ理論ではよく使われるvisibility researchnoの１例である．

　今回のコラムでは，フバータルの美術館問題（art gallery problem）

［Ｑ］ｗ枚の壁をもつ美術館を守るのに必要な最小の監視員（または監視カメラ）の数ｇ（ｗ）はいくつか？

とそのバリエーションを取り上げたい．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　この問題は計算幾何学（離散幾何学と最適化が混じった分野）の問題に関係していて，フバータルによって提示され，証明された．

［Ａ］　　ｇ（ｗ）＝［ｗ／３］

であるが，ガウス記号中の３は三角形分割に関係していることはよく知られている．

　美術館が凸であれば監視カメラは１台で済むから，非凸なｗ角形とする．これをｗ−３本の対角線で，ｗ−２個の三角形に分割することができる．また，三角形分割された図形は３色（Ｂ，Ｒ，Ｙ）を使って，隣接する２頂点がすべて異なる色になるように塗り分けることができる．たとえば，２つの頂点がＲとＢであったならば，もう一つの頂点はＹとすればよい．

　すると最低でも３色のうちどれかひとつの色は［ｗ／３］回出現することになる．その色の頂点に監視カメラを設置すれば美術館全体を見守ることができるというわけである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［Ｑ］ｗ枚の壁とｈ個の穴をもつ美術館を守るのに必要な最小の監視員（または監視カメラ）の数ｇ（ｗ）はいくつか？

［Ａ］　　ｇ（ｗ，ｈ）＝［（ｗ＋ｈ）／３］

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［Ｑ］ｗ枚の壁をもつ直角美術館を守るのに必要な最小の監視員（または監視カメラ）の数ｇ（ｗ）はいくつか？

［Ａ］直角美術館はすべて凸四角形分割をもち，

　　ｇ（ｗ）＝［ｗ／４］

である．ガウス記号中の４は四角形分割に関係している．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝