■多角形の三角形分割と多面体の四面体分割
まず,フバータルの美術館問題とそのバリエーションを取り上げたい.この問題は計算幾何学(離散幾何学と最適化が混じった分野)の問題に関係していて,フバータルによって提示され,証明された.
===================================
[Q]w枚の壁をもつ美術館を守るのに必要な最小の監視員(または監視カメラ)の数g(w)はいくつか?
[A] g(w)=[w/3]
であるが,ガウス記号中の3は三角形分割に関係していることはよく知られている.
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
[Q]w枚の壁とh個の穴をもつ美術館を守るのに必要な最小の監視員(または監視カメラ)の数g(w)はいくつか?
[A] g(w,h)=[(w+h)/3]
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
[Q]w枚の壁をもつ直角美術館を守るのに必要な最小の監視員(または監視カメラ)の数g(w)はいくつか?
[A]直角美術館はすべて凸四角形分割をもち,
g(w)=[w/4]
である.ガウス記号中の4は四角形分割に関係している.
===================================
フバータルの美術館問題は任意の多角形はすべて三角形分割をもつことに基づいている.それでは,任意の多面体はすべて四面体分割をもつだろうか?
これには辺を使った四面体分割をもたない反例が知られている.
===================================