■多面体的組み合わせ論(その6)
ミンコフスキーの格子点定理(ミンコフスキーの第1定理)は数の幾何学の基礎となっているのですが,格子点定理は次のように述べることができます.
「平面(n次元空間)上の任意の単位格子において,1つの格子点を中心として1辺の長さが2の正方形(面積4の平行四辺形,面積2^nの中心対称な凸体)を任意の向きにおいてみると,内部あるいは境界上にもうひとつの格子点が必ず存在する.」
今回のコラムでは,これの双対と考えられる「多面体による球体近似」定理(ミンコフスキーの第2定理)
2^n/n!≦vol(K)≦2^n
を紹介します.
===================================
【1】ミンコフスキーの第2定理
一般に中心対称な凸体(もっと一般的に0が重心であるような凸体)Kに対して,
2^n/n!≦vol(K)≦2^n
はミンコフスキーの第2定理と呼ばれています.
すなわち,Kの体積は1辺の長さ2の立方体とそれを切断した直角三角錐の体積の中間になるというものです.冒頭で紹介したように両者は数学的双子なのですが,それにしてもよく似ていると思いませんか?
===================================
【2】マーラーの不等式
立方体領域:K={|x1|≦1,・・・,|xn|≦1}の体積は2^n,また,正八面体領域:K~={|x1|+・・・+|xn|≦1}の体積は2^n/n!で与えられます.両者は極双対集合です.
中心対称な凸体(もっと一般的に0が重心であるような凸体)Kとその極双対集合K~に対して,マーラーの不等式
4^n/(n!)^2≦vol(K)vol(K~)≦4^n
成立します.
===================================
【3】ブラシュケ・サンターロの不等式
ブラシュケ・サンターロの不等式は
c1^n/n!≦vol(K)vol(K~)≦c2^n/n!
というものです.
前節のマーラーの不等式は最良のものではなく,定理の上限については
vol(K)vol(K~)≦vol(B^n)^2=π^n/Γ^2(n/2+1)が成り立ちます.下限については
4^n/n!≦vol(K)vol(K~)
が予想されています(マーラー予想).
===================================
【4】ブルン・ミンコフスキーの不等式
ミンコフスキー和A+Bは図形Aを構成する点の位置ベクトルと図形Bを構成する点の位置ベクトルの和全体がなす図形であり,一方の図形の原点がもう一方の図形の境界上を一周するように平行移動させたときにできる和集合である.(いろいろな使い道があるものだと感心したのだが)ロボットの原点が踏み込んではならない領域を表すのに応用することができる.
日本の国土をA,半径rの円板をBとして,陸地の各点にこの円板を貼り付けることによって定まる領域がA+Bである.すなわち,陸地からの距離がr以下の海の部分を陸地に加えた領域がミンコフスキー和A+Bである.
A,B,A+Bの3つの面積の関係を述べたものがブルン・ミンコフスキーの不等式である.これまでは平面での場合を述べたが,一般のn次元図形に対しても不等式
|A+B|^1/n≧|A|^1/n+|B|^1/n
が成立する(平面図形の場合はn=2).等号成立はAとBは相似の位置にあるか,またはAはBの平行移動であるときである.
また,2つの凸図形K0,K1が与えられたとき,K0からK1への連続変形
Kt=(1−t)K0+tK1 (0≦t≦1)
においては
|Kt|^1/n≧(1−t)|K0|^1/n+t|K1|^1/n
が成り立つ.
===================================