ある図形を描く場合，頂点の座標をすべて求めそれらを正しく結ぶことができれば理想なのですが，そのような手が使えない場合はマッピングすることになります．

　ところが，旧式のＰＣでＦ2＝０空間のマッピングを試みると，計算時間が莫大でしかも粗い計算しかできません．なにせ最新のＰＣでも何十分もかかる計算なのですから・・・．すなわち，マッピングはＰＣのスペックに依存していて，計算アルゴリズムの差が明確に現れない方法なのです．

　アルゴリズムを工夫して，その結果，１０倍も速い計算方法を生み出すことこそ創造の醍醐味であって，力ずくで労力さえかければ必ずできるようなプログラムは，小生的にはあまり好みとはいえない解法です．そこで，今回のコラムでは旧型のＰＣであっても数分以内にＦ2＝０空間のほとんどの領域（概形）を網羅できるという探索的アルゴリズムについて紹介したいと思います．

　ただし，近似解の近似ですから，この探索的アルゴリズムでもって多面体の正確な断面の形を決めることは困難であり，あくまでも許容できる範囲の計算精度と計算速度をもった断面の概形ということになります．

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

【１】探索的アルゴリズム

　ｆkをｎ次元多面体のｋ次元面の数とし，

　　（ｆ0，ｆ1，・・・，ｆn-2，ｆn-1）

を構成要素とするｎ次元正多胞体では，組み合わせ的方法によって，ｋ次元胞数ｆkが求められます．

　たとえば，正単体では

　　ｆk＝（ｎ＋１，ｋ＋１）

なのですが，ｋ＝ｎ−１のときｆk＝ｎ＋１であって，胞数はｎ＋１と計算されます．同様に，双対立方体では

　　ｆk＝２^k+1（ｎ，ｋ＋１），ｋ＝ｎ−１のとき，ｆk＝２^n

立方体では

　　ｆk＝２^n-k（ｎ，ｋ），ｋ＝ｎ−１のとき，ｆk＝２ｎ

となります．

　もちろん，

　　正単体：ｆk＝（ｎ＋１，ｋ＋１）

　　双対立方体：ｆk＝２^k+1（ｎ，ｋ＋１）

　　立方体：ｆk＝２^n-k（ｎ，ｋ）

はオイラー・ポアンカレの定理：

　　ｆ0−ｆ1＋ｆ2−・・・＋（−１）^(n-1)ｆn-1＝１−（−１）^n

すなわち，ｎが奇数なら２，偶数なら０を満たします．この定理は正多胞体に限らず，ｎ次元凸多胞体について常に成立します．

　ｎ次元立方体（正２ｎ胞体）の場合，

　　頂点数：　２^n，

　　稜数：　　２^(n-1)ｎ，

　　四角形数：２^(n-3)ｎ（ｎ−１）

となるのですが，このことからｎ次元直方体の頂点数＜稜数であり，カーネルの形の概略を知るには稜を基線とすればよいことがわかります．

　このプログラムでも稜に平行な直線上を探索することによって，カーネルを求めています．その考え方はシンプレックス法に似ていますが，頂点上や稜上に解があることはほとんどなく，内部探索を行わなければなりません．

　探索的アルゴリズムは妥協の産物であって，この方法で得られる領域はどうしても探索漏れをなくすことはできませんから，（その１）で求めたカーネルよりやや小さめに描かれます．結局，正確な形を描くことを断念し，許容範囲の計算所要時間と計算精度をもつ近似計算をすることにしたのですが，しかし，短時間で断面の概形を知りたいときには簡易探索でもまあまあかというのが率直な感想です．

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

【２】実行例

　マッピング解（その１）のほとんどの領域を短時間でカバーすることができました．

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

【３】凸包アルゴリズム

　コラム「ロボットアームと６次元直方体」では，輪郭線処理としてｎ次元立方体の特性を利用した方法を紹介しました．この方法を応用するとｎ次元双対立方体でもｎ次元単体の場合でも描けます．→「高次元の正多胞体」

　しかし，平行２ｎ面体の断面の形はそれらに較べて規則的ではないため，このような輪郭線処理を行うことができません．そのような場合の一般的な解法として凸包（convex hull）アルゴリズムが知られています．

　平行２ｎ面体の頂点の数は２^nであり，ｎの増加とともに指数関数的に増えますし，２^n個から２次元に射影した場合の頂点数２ｎ個を探し出すのはかなりの計算量が必要となります．

　単純に考えると，平面上のｎ個の点の凸包を構成するアルゴリズムの計算量はＯ（n^3）となりそうですが，ここで作成したアルゴリズムではＯ（nlogn）となったので，格段の性能のよさにびっくりさせられました．

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

【４】補足（高次元の球と立方体の断面の体積）

（１）ボールの不等式

　ｎ次元単位立方体の断面の体積の最大値について考えてみましょう．

　１辺の長さが１の正方形（２次元単位立方体）の切り口は単に線分になるから，その長さが最大となるのは対角線であって，最大値は√２となる．対角線とは頂点とその対角にある頂点を結ぶ線分で，正方形の原点を通るものである．

　また，（３次元）単位立方体の断面は，３角形・４角形・５角形・６角形などいろいろな形をとるが，立方体の中心を通り，辺とその対蹠に位置する辺を含む平面で切ったとき，断面積は最大値√２になる．

　２次元・３次元での問題は，４次元の場合あるいは考察をもっと高次元化していくこともできますが，ｎ次元単位立方体を中心を通るｎ次元超平面で切ったとき，その切り口の体積（断面積）Ｖは，

　　１≦Ｖ≦√２

であることが，ボールによって証明されています（1986年）．

　ボールの不等式のいいところは，Ｖが次元によらず，√２で上から評価されている点です．ボールの不等式は２，３次元でも一般次元でも同じ形で成立しましたが，こんなことがつい最近まで証明されなかったのは，一般次元における幾何の問題は，高い次元になると多くの反例が作れるからだと想像されます．

（２）ビューズマンの定理とボールの反例

　一方，半径ｒのｎ次元超球の体積はＶnｒ^nですから，体積を１とするｒの値はＶn^(-1/n)で与えられます．また，ｎ次元超球の中心を通る超平面による切り口は（ｎ−１）次元超球であり，その体積はＶn-1ｒ^(n-1)で表されますから，体積が１の超球の切り口の体積は

　　Ｖn-1・Ｖn^(1/n-1)

となります．

ｎ Ｖn-1・Ｖn^(1/n-1)

２ 1.128

３ 1.209

４ 1.265

５ 1.307

６ 1.339

７ 1.365

８ 1.387

９ 1.405

10 1.420

11 1.434

12 1.445

13 1.456

14 1.465

　体積１の１０次元超球について，その実際の値を計算してみると１．４２０３・・・となり，体積１の１０次元単位立方体の超平面による切り口の体積√２よりも大きくなります．ここで，半径ｒをほんの少し縮小した超球を考えてみると，単位立方体より断面積は大きいが体積は小さい例を作れることがわかります．

　ところで，３次元空間内の２つの点対称凸体Ｋ，Ｋ’に関して，凸体の中心を通る任意の平面について，断面積の不等式

　　Ａ（Ｋ）＞Ａ（Ｋ’）

が成り立つならば，体積についても不等式

　　Ｖ（Ｋ）＞Ｖ（Ｋ’）

が成り立つことが知られています（ビューズマンの定理，1953年）．

　すなわち，１０次元のボールの例は，

　　Ａ（Ｋ）＞Ａ（Ｋ’）

であっても

　　Ｖ（Ｋ）＜Ｖ（Ｋ’）

という高次元におけるビューズマンの反例になっているのです．

　さて，１０次元以上の一般次元であれば，このような反例が具体的に与えられるのでしょうか？

　　Ａn＝Ｖn-1・Ｖn^(1/n-1)

とおくと，

　　Ａn/Ａn-2＝Ｖn-1・Ｖn^(1/n-1)/Ｖn-3・Ｖn-2^(1/(n-2)-1)

ですから，ｎ→∞のとき，

　　Ａn/Ａn-2→(Ｖn/Ｖn-2)^(1/n)=(2π/n)^(1/n)→１

これより，次元を高くすれば断面積はある極限値に収束しそうです．ｎ→∞のとき，Ｖn-1→０，Ｖn→０ですが，Ａn＝Ｖn-1・Ｖn^(1/n-1)の極限値を求めてみることにしましょう．

　Ｖn=π^(n/2)/(n/2)!より，

　　Ａn＝{(n/2)!}^(1-1/n)/{(n-1)/2}!

これを有名なスターリングの近似公式

　　ｋ！＝√２π・ｋ^(k+1/2)・exp（−ｋ）

を使って書き直してみましょう．簡約化すると

　　Ａn→(n/2)^(n/2)/{(n-1)/2}^(n/2)

　　　　＝{n/(n-1)}^(n/2)

　　　　＝{(1+1/(n-1))^(n-1)}^(1/2)*{n/(n-1)}^(1/2)

　　　　→e^(1/2)

したがって，極限値√ｅ＝１．６４８７・・・に収束することがわかります．

　　√２＜√ｅ＜√３

ですから，これは高次元ではボールの反例がいくらでも作れることを意味しています．

　逆に，９次元以下ではボールの反例は作られませんが，それ以外のビューズマンの反例については，５次元以上で存在することが証明されています（1992年）．しかし，４次元で反例が作れるかどうかは，現在，未解決の問題として残されています．

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