より近い集合の評価法

質問

n次元空間内で定義される凸集合をAとします．
Aの部分集合である凸集合BとCがあったとします．
このとき，Aの要素をより多く含む集合がBなのかCなのかを
定量的に評価する方法を教えてください．

回答No.4

stomachman

どうやら、「n次元ユークリッド空間において、有限の超体積を持つ凸領域Aが与えられたとき、Aに含まれる凸m面体Bのうち超体積が最大のものCをみつけるアルゴリズムを求む」という（計算幾何学の）問題をお考えなのではないでしょうか。
　ここで「超体積」と呼んだのはANo.3に示した通り、被積分関数が1であるようなn重積分であって、1次元なら長さ、2次元なら面積、3次元なら体積になり、n次元でも全く同様に計算できます。（なので普通は、何次元の話であっても単に「体積」と呼ばれます。）

　余談ながら、仮に「Bの頂点がm個」という問題だったとしても、m＞n+1の場合には、Bの各頂点がAの表面上を走るとき、Bの面が自己交差していないかどうかを心配しなくてはならない。まして「面がm個」という条件だとBには様々な形があり得るから、かなり難しい問題じゃないでしょうか。
　一方、Aが具体的に決まっていて、その性質を利用してCの候補をうんと絞れる、ということがあると話がだいぶ変わって来ます。たとえば「Aは凸多面体である」という条件があれば、Cの頂点はAの頂点以外のところには存在しないでしょう（要証明）から、Aの頂点のうちどれを選んでBを作るか、という離散的な組み合わせの問題になるでしょう。また、ANo.2のコメント欄で挙げられた例では（イマヒトツよくわからん例なのですが、どうやら）3次元の話なのに（円弧上の点を決めるという）1次元の問題に帰着出来てい（るようであ）る。それは、（「Bは4面体であり、従って4(=n+1)個の頂点を持つ、という条件があって、このため自己交差の心配が要らない」ということだけでなく、）Aの性質「頂点を3つだけ持つから、Bの頂点のうち3個は決まってしまう」を利用できたからですよね。つまり、どんなAを持って来るかによってアプローチが全然違って来るんですね。

お礼

所用によりずっとパソコンを操作する機会がありませんでした．
お礼のコメントが遅くなり大変失礼しました．
この間に有益なご回答をいただきましてありがとうございました．

具体例で言いますと，例えば以下のことを考えています．

「集合Σ1={(x1,x2,x3)|x1>0,x2>0,x3>0,x1-2x3>0,x1x2-x2^2-x3^2>0}
　（これは，原点を頂点とし各変数の正の方向に無限に広がる半円錐集合の内側の集合になります．）
このとき，
集合Σ2={(x1,x2,x3)|t11・x1+t12・x2+t13・x3>0,t21・x1+t22・x2+t23・x3>0,t31・x1+t32・x2+t33・x3>0}
がΣ1の部分集合となり，かつ，平面x1=c(cは任意の正数)でΣ2をカットした断面積S(tij)が
最大となる定数tij (i,j=1,2,3)を求めよ」
という最適化問題の定式化です．

x1=cでΣ1を切り取ると，断面が半円（中心(y,z)=(0,c/2),半径c/2の円の内部のうち
x2>0の部分）で，面積が有限になるのでx1=cを選んでいます．Σ2の断面は3角形です．

図形から最適値は，t11=1,t12=-1,t13=-1,
t21=0,t22= 1,t23=-1,
t31=0,t32= 0,t33= 1
すなわち，断面が3点(y,z)=(0,0),(y,z)=(0,c),(y,z)=(c/2,c/2)を
頂点とする2等辺三角形となるときとわかります．

これを図形からではなく，

Find optimal tij which maximize S(tij)
s.t. Σ2⊂Σ1

という最適化問題を考え，3次元空間の問題の定式化からn次元の問題；

与えられた凸集合(x1,x2,...,xn)（一般にすべての要素が正で，無限に広がりを持つ）に対して
集合Σ2={(x1,x2,...,xn)|
t11・x1+t12・x2+...+t1n・xn>0,
t21・x1+t22・x2+...+t2n・xn>0,
......

tn1・x1+tn2・x2+...+tnn・xn>0}

がΣ1の部分集合となり，かつ，ある超平面でΣ2カットした断面積S(tij)（測度？）が
最大となる定数tij (i,j=1,2,...,n)を求めるよ」

の具体的定式化を類推することです．これを凸計画問題などの解法で数値的に解くことを
考えています．

おっしゃる通り，Σ1がどんな集合かで定式化が変わるかもしれません．

回答No.3

stomachman

ANo.2へのコメントについてです。

> 3次元空間の原点を通り各座標軸の正の方向に
> 開いた半円錐の内側の集合をA

　「各座標軸の正の方向に開いた半円錐」？？　多分直交座標を使ってユークリッド空間の話をしているんだろうな、ということ以外、よく分からんです。できればAを(x,y,z)の集合としてA={(x,y,z) | …}のように書いてもらえると

> 図形的には体積が尺度となり，ｎ次元空間では，おっしゃるような測度が尺度になると
考えています．

　問題がよくわからんのですが、なぜ、ｎ次元空間の時にも測度として体積
　　V = ∫[(x1,x2,…,xn)∈B]dx1dx2…dxn
を使わないのでしょう？ もし、「部分集合である錐Bの頂点はどれも原点にあるけど、錐Bは無限に伸びていて底面がないから体積もない」というような話であるなら、適当な面Sで切った断面S∩Bの面積を測度として用いて比較すれば良いでしょう。（もちろん、Sとしてたとえば球面(x1^2+…+xn^2=1など)で切るか平面(x1+…+xn=1など)で切るかで、測度が違って来る訳ですが。）

回答No.2

stomachman

ANo.1へのコメントについてです。

　無限集合ってのはやっかいな物でして、無限集合同士で「どっちが多くの要素を含むか（濃度）」を比べるには、まず要素同士の1:1対応を考えます。たとえば、全ての有理数の集合Qは全ての自然数の集合Nや全ての整数の集合Zと丁度同じ濃度であり、これらは可算無限集合と呼ばれます。一方、0から1までの実数の集合[0.1]は、Qとどう対応付けてもまだ余ってしまう。つまり、[0,1]の方がQよりも真に多くの要素を含むんです。
　でも、こういうやりかただと、
　　B = {x| xは実数で、0＜x＜1}
　　C = {x| xは実数で、1＜x＜3}
はどちらも同じ濃度、という以上の話にはなりません。

　「いや、そういうんじゃなくてー、大きさを比べたいんだよぉ。わかるでしょ？」という場合に測度というものを使います。測度というのはある集合Aの部分集合から非負の実数への関数で、
　　任意のX⊂A, Y⊂Aについて、X∩Y=∅(空集合)のとき、μ(X∪Y)=μ(X)+μ(Y)　
　　μ(∅)=0
を満たせば何でも良いんです。たとえば
　　μ(X)=∫dx (積分は x∈X となるxについての定積分）
を測度として採用すれば、μ(B)＜μ(C)です。しかし、
　　μ(X)=∫|1/x| dx (積分は x∈X となるxについての定積分）
を使うと結果は逆になります。

（注意：これは厳密な議論ではありません。というのは「x∈X となるxについての定積分」はどんなXについてでも定義できるわけではない。実は話は逆で、そのような積分を定義するにはどうすればいいか、という考察の中から測度という概念が生まれてきたのです。）

　測度のうちで、回転や平行移動で不変（この場合なら、
　　Z={ z | x∈X, z=x+C}
や
　　Z={ z | x∈X, z=-x}
について μ(X)=μ(Z) ）であるような測度に限定すると、これは体積（の定数倍）になるわけですが、そういう限定をしなければならない、という理由がご質問の場合にはありません。むしろ、むやみな限定を付けない事によって、目的・用途に応じたいろんな応用が可能になるんです。たとえば、ある空間Sがぐにゃりと歪んで空間Aに写像されているとしますと、Sにおいて同じ体積をもつ集合u,vのAにおける像X,YのAにおける体積はもはや等しくないけれども、両者の測度が同じになるような測度をA上で定義できる場合が（写像によっては）あるわけです。

お礼

詳しく解説していただきましてありがとうございました．

今考えている問題は，たとえば3次元の場合，3次元空間の原点を通り各座標軸の正の方向に
開いた半円錐の内側の集合をAと考え，これの部分集合となる三角錐の内側の集合の中で
最もAに含まれる要素を多く含む三角錐を定量的尺度で選ぶことです．

図形的には体積が尺度となり，ｎ次元空間では，おっしゃるような測度が尺度になると
考えています．

3次元空間では図から明らかに，半円錐の断面の半円の直径部分と円弧の中点で作られる三角形を断面とする三角錐が体積最大となることがわかります．

このような話をｎ次元に拡張し，与えられた集合Aの部分集合の中で
測度が最大になる超ｎ面体を定量的に探してくるという最適化問題を解きたい
のですが．．．具体的にどのような測度を定義すればよいのかわからないので
質問をした次第です．

私の質問が説明不足でわかりにくいにもかかわらず，丁寧に回答してくださいまして
誠にありがとうございました．測度を目的関数とする最適化問題を考えればよいことが
わかり，それが確認できただけでもありがたく思います．

回答No.1

stomachman

> Aの部分集合である凸集合BとCがあったとします．
> このとき，Aの要素をより多く含む集合がBなのかCなのか

　凸集合に限る理由などないし、集合Aにも出番がありません。

○ B,Cが有限集合なら、BとCのうち濃度（要素の個数）の大きい方。
○ B,Cのうち一方が有限集合、他方が無限集合なら、無限集合の方。
○ 無限集合BがCの部分集合ならC、無限集合CがBの部分集合ならB。
○ B,Cが無限集合で、どちらがどちらの部分集合でもない場合、「体積」に相当する尺度（「測度」といいます）としてどんなものを用いるかによって、答はどうとでもなります。

お礼

早々のご回答に感謝申し上げます。

今考えていることは

> ○ B,Cが無限集合で、どちらがどちらの部分集合でもない場合、

に相当します。この場合、

> 「体積」に相当する尺度（「測度」といいます）としてどんなものを用いるかによって、答はどうとでもなります。

ということですが、代表的な測度には具体的にどのようなものがありますか？　
それと、どのようにでもなるというあたりがよく理解できません。
よろしければご教授ください。