［参］フバータル「線形計画法」啓学出版

にしたがって，多面体のすべての頂点を求めてみた．阪本ひろむ氏によると

［１］理論的には計算量が多すぎる．

［２］ほぼ同内容のことは「線形不等式」（岩波基礎数学講座）にも記載があるようだ．（ただし，専門用語が全然違うが・・・）

［３］その後，VertexEnum.mというパッケージを入手した．フバータルの本と同等またはそれより合理的な方法をとっている様である．

［４］VectEnum.mにより高速化が実現された．フバータルの方法だとn=11のとき4時間ぐらい．VectEnum.mだと数分でとけた．n=8ぐらいまでは両者の実行時間はたいして変わらない．

［５］フタバールの本は「近傍」云々の手順が煩雑な気がする．あの本がでてからかなり時間がたっているので，良い方法が見つかったのかも．フーリエ・モツキン法の可能性あり．今後の研究課題としたい．

　今回のコラムでは，フバータル繋がりで，美術館問題とそのバリエーションを取り上げたい．この問題は計算幾何学（離散幾何学と最適化が混じった分野）の問題に関係していて，フバータルによって提示され，証明された．

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

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

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

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

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

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

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

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

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

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

　　ｇ（ｗ）＝［ｗ／４］

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

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