「《双対変換》」の版間の差分

2007年8月7日 (火) 02:15時点における最新版

【そうついへんかん (dual transformation) 】

　ORの様々な理論において，双対性は重要な役割を果たす．これは計算幾何でも同様で，特に双対性に対応する変換によって，ある問題を別のよりわかりやすい問題に変換して解くことができる．詳細については， [1, 2, 3]参照．

　まず， $d\,$ 次元空間の2次曲面の極と極面に関する極変換について述べる． $d\,$ 次元空間の超平面は，

$a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{d}x_{d}+a_{d+1}=0\,$

で表される． $d\,$ 次元空間の2次曲面は， $(d+1)\times (d+1)\,$ 対称行列 $A\,$ と $(d+1)\,$ 次元ベクトル ${\boldsymbol {x}}=(x_{1},x_{2},\ldots ,x_{d},1)^{\top }\,$ を用いて， ${\boldsymbol {x}}^{\top }A{\boldsymbol {x}}=0\,$ と表せる．点 $p=({\boldsymbol {p}})=(p_{1},p_{2},\ldots ,p_{d})^{\top }\,$ に対して，方程式

${\boldsymbol {x}}^{\top }A({\boldsymbol {p}},1)=(x_{1},x_{2},\ldots ,x_{d},1)A(p_{1},p_{2},\ldots ,p_{d},1)^{\top }=0\,$

をみたす超平面 $D(p)\,$ を対応させる．逆に定数ベクトル $p=(p_{1},p_{2},\ldots ,p_{d})^{\top }\,$ を用いて ${\boldsymbol {x}}^{\top }A({\boldsymbol {p}},1)=0\,$ と書ける超平面 $h\,$ に対して点 $D(h)=p\,$ を対応させる．明らかに $D(D(p))=p,D(D(h))=h\,$ であり，この変換 $D\,$ は双対変換である．点 $p\,$ と超平面 $D(p)\,$ (点 $D(h)\,$ と超平面 $h\,$ ) は，2次曲面 ${\boldsymbol {x}}A{\boldsymbol {x}}^{\top }=0\,$ に関する極と極面となる．2次曲面としては，球や面がよく用いられる．

　以下，簡単のため2次元の場合を述べる．放物線 $y=(x^{2})/2\,$ を用いれば，点 $p=(p_{x},p_{y})\,$ に対する極線 $D(p)\,$ は $y=p_{x}x-p_{y}\,$ となる． $y\,$ 軸に平行でない直線 $h\,$ は，傾き $p_{x}\,$ と $y\,$ 切片のマイナスの $p_{y}\,$ を用いて $y=p_{x}x-p_{y}\,$ と表せ， $h\,$ の極 $D(h)\,$ は点 $(p_{x},p_{y})\,$ となる． $p\,$ が放物線上にあるとき， $p\,$ での接線が $D(p)\,$ となる．

　この変換は，接続関係(上下関係)を保存する．すなわち，点 $p=(p_{x},p_{y})\,$ と直線 $h\colon y=q_{x}x-q_{y}\,$ およびその双対変換 $D(p)\colon y=p_{x}x-p_{y}\,$ と $D(h)=(q_{x},q_{y})\,$ に対して $p_{y}+q_{y}\,$ と $p_{x}q_{x}\,$ の大小関係に応じて以下のことが成立する．

(a) 点

p\,

が直線

h\,

上にあるとき，およびそのときのみ，点

D(h)\,

は直線

D(p)\,

上にある

(p_{y}+q_{y}=p_{x}q_{x})\,

．

(b) 点

p\,

が直線

h\,

を境界とする上半平面(下半平面)にあるとき，およびそのときのみ，点

D(h)\,

は直線

D(p)\,

を境界とする上半平面(下半平面)にある．

　接続関係(上下関係)の不変性は，2次曲線として円や楕円を用いて変換を定義しても成立し，一般の $d\,$ 次元空間でも成立する．点の集合はそれだけで扱うとばらばらで考えにくいため，アルゴリズム的にも上下関係など関係式がわかるように，この双対変換を適用して，直線(超平面)の集合からできる平面(空間)の交差図形を利用することがしばしば行われる．このとき，双対変換で1対1に対応するとともに，この関係式が保存され，直線(超平面)が交わって空間を分割することから問題がとらえやすくなる．このような直線(超平面)による平面(空間)の交差図形をアレンジメントと呼ぶ．アレンジメントの1つのセルに対応する凸多面体についても，ファセットを含む超平面で定まる半空間の交わりとしても，端点の凸包としても表せる．これは双対性の現れで，すべての次元の構成要素であるフェイス全体がなす束でも，対応する束の上下を反転すれば同じとなる双対性が成り立つ．したがって，双対性から半空間の交わりを求めることと，点集合の凸包を求めることとは，アルゴリズムの計算量の観点からは同じである．

　2次曲線として円を用いた場合の極変換も重要である．このとき，原点以外の点 $(p_{x},p_{y})\,$ は直線 $p_{x}x+p_{y}y-1=0\,$ に変換される．この直線は，原点からの距離が原点と元の点 $(p_{x},p_{y})\,$ の距離の逆数になっており，原点と元の点を結ぶ直線に垂直で，原点に関して元の点と同じ側の直線となる．

　円に関する極変換の変形に反転がある．反転は，原点以外の点 $(p_{x},p_{y})\,$ を上の極変換を施した直線への原点からの垂線の足に対応させる．反転により，原点を通る円は直線に変換される．この変換をもう1次元高い空間で行うと，球と平面の間の変換が得られる．たとえば、 $(0,0,1)\,$ を中心とする半径1の球面を基本となる二次曲面として採用した場合の極変換では， $xy\,$ 平面は $(0,0,1/2)\,$ を中心とする半径 $1/2\,$ の球へ変換される．この変換は立体射影 (stereographic projection) と呼ばれる．

　さらなる変形として，画像処理で特に用いられているハフ変換 (Hough transformation) がある．2次元の直線を原点からこの直線への垂線の距離 $r\,$ と直線と $x\,$ 軸がなす角度 $\theta \,$ で表して，それを

直線　 $x\sin \theta +y\cos \theta =r\ \mapsto \,$ 　点　 $(r,\theta )\,$

と変換する．Hough変換は，画像からの直線成分やさらには楕円などを抽出することによく用いられる．

　極変換は2次曲線を核としていたが，核を一般の凸関数に拡張することもできる．この場合の双対変換は，Legendre変換と一般に呼ばれ，特に最適化の分野ではFenchelの共役性として知られている．この場合，核の凸関数の共役凸関数が定義でき，放物線 $y=(x^{2})/2\,$ は自己共役になっている．凸関数の共役性は，凸解析の基本概念である．

参考文献

[1] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.　邦訳(今井浩, 今井桂子訳), 『組合せ幾何学のアルゴリズム』，共立出版, 1995.

[2] F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985. 邦訳 (浅野孝夫, 浅野哲夫訳) , 『計算幾何学入門』, 総研出版, 1992.

[3] 佐々木建昭, 今井浩, 浅野孝夫, 杉原厚吉, 『計算代数と計算幾何』, 岩波応用数学[方法9], 岩波書店, 1993.

@@ 3行目: / 3行目: @@
 　ORの様々な理論において，双対性は重要な役割を果たす．これは計算幾何でも同様で，特に双対性に対応する変換によって，ある問題を別のよりわかりやすい問題に変換して解くことができる．詳細については， [1, 2, 3]参照．
-　まず，$d$次元空間の2次曲面の極と極面に関する[[極変換]]について述べる．$d$次元空間の超平面は，
+　まず，<math>d\, </math>次元空間の2次曲面の極と極面に関する[[極変換]]について述べる．<math>d\, </math>次元空間の超平面は，
-　a_1x_1+a_2x_2+\cdots+a_dx_d+a_{d+1}=0
-で表される．$d$次元空間の2次曲面は，$(d+1)\times (d+1)$対称行列$A$と$(d+1)$次元ベクトル$ \hbox{\boldmath$x$}=(x_1,x_2,\ldots,x_d,1)^{\top}$を用いて，$ \hbox{\boldmath$x$}^{\top} A \hbox{\boldmath$x$}=0$と表せる．点$p=( \hbox{\boldmath$p$})=(p_1,p_2,\ldots,p_d)^{\top}$に対して，方程式
+<center>
+<math>a_1x_1+a_2x_2+\cdots+a_dx_d+a_{d+1}=0\, </math>
+</center>
- \hbox{\boldmath$x$}^{\top} A( \hbox{\boldmath$p$},1)=(x_1,x_2,\ldots,x_d,1)A
-(p_1,p_2,\allowbreak\ldots,p_d,1)^{\top}=0
-をみたす超平面$D(p)$を対応させる．逆に定数ベクトル$p=(p_1,p_2,\ldots,p_d)^{\top}$を用いて$ \hbox{\boldmath$x$}^{\top} A( \hbox{\boldmath$p$},1)=0$と書ける超平面$h$に対して点$D(h)=p$を対応させる．明らかに$D(D(p))=p$,$D(D(h))=h$であり，この変換$D$は[[双対変換]]である．点$p$と超平面$D(p)$(点$D(h)$と超平面$h$)は，2次曲面$ \hbox{\boldmath$x$} A \hbox{\boldmath$x$}^{\top}=0$に関する極と極面となる．2次曲面としては，円や放物線がよく用いられる．
+で表される．<math>d\, </math>次元空間の2次曲面は，<math>(d+1)\times (d+1)\, </math>対称行列<math>A\, </math>と<math>(d+1)\, </math>次元ベクトル <math>\boldsymbol{x}=(x_1,x_2,\ldots,x_d,1)^{\top}\, </math>を用いて， <math>\boldsymbol{x}^{\top} A \boldsymbol{x}=0\, </math>と表せる．点<math>p=( \boldsymbol{p})=(p_1,p_2,\ldots,p_d)^{\top}\, </math>に対して，方程式
-　以下，簡単のため2次元の場合を述べる．放物線$y=(x^2)/2$を用いれば，点$p=(p_x,p_y)$に対する極線$D(p)$は$y=p_xx-p_y$となる．$y$軸に平行でない直線$h$は，傾き$p_x$と$y$切片のマイナスの$p_y$を用いて$y=p_xx-p_y$と表せ，$h$の極$D(h)$は点$(p_x,p_y)$となる．$p$が放物線上にあるとき，$p$での接線が$D(p)$となる．
-　この変換は，接続関係(上下関係)を保存する．すなわち，点$p=(p_x,p_y)$と直線$h\colon y=q_xx-q_y$およびその双対変換$D(p)\colon y=p_xx-p_y$と$D(h)=(q_x,q_y)$に対して$p_y+q_y$と$p_xq_x$の大小関係に応じて以下のことが成立する．
+<center>
+<math>\boldsymbol{x}^{\top} A( \boldsymbol{p},1)=(x_1,x_2,\ldots,x_d,1)A
+(p_1,p_2,\ldots,p_d,1)^{\top}=0\, </math>
+</center>
-　(a) 点$p$が直線$h$上にあるとき，およびそのときのみ，点$D(h)$は直線$D(p)$上にある($p_y+q_y=p_xq_x$)．
-　(b) 点$p$が直線$h$を境界とする上半平面(下半平面)にあるとき，およびそのときのみ，点$D(h)$は直線$D(p)$を境界とする上半平面(下半平面)にある．
+をみたす超平面<math>D(p)\, </math>を対応させる．逆に定数ベクトル<math>p=(p_1,p_2,\ldots,p_d)^{\top}\, </math>を用いて <math>\boldsymbol{x}^{\top} A( \boldsymbol{p},1)=0\, </math>と書ける超平面<math>h\, </math>に対して点<math>D(h)=p\, </math>を対応させる．明らかに<math>D(D(p))=p,D(D(h))=h\, </math>であり，この変換<math>D\, </math>は[[双対変換]]である．点<math>p\, </math>と超平面<math>D(p)\, </math> (点<math>D(h)\, </math>と超平面<math>h\, </math>) は，2次曲面<math> \boldsymbol{x} A \boldsymbol{x}^{\top}=0\, </math>に関する極と極面となる．2次曲面としては，球や面がよく用いられる．
-　接続関係(上下関係)の不変性は，2次曲線として円や楕円を用いて変換を定義しても成立し，一般の$d$次元空間でも成立する．点の集合はそれだけで扱うとばらばらで考えにくいため，アルゴリズム的にも上下関係など関係式がわかるように，この双対変換を適用して，直線(超平面)の集合からできる平面(空間)の交差図形を利用することがしばしば行われる．このとき，双対変換で1対1に対応するとともに，この関係式が保存され，直線(超平面)が交わって空間を分割することから問題がとらえやすくなる．このような直線(超平面)による平面(空間)の交差図形を[[アレンジメント]]と呼ぶ．アレンジメントの1つのセルに対応する[[凸多面体]]についても，ファセットを含む超平面で定まる半空間の交わりとしても，端点の凸包としても表せる．これは双対性の現れで，すべての次元の構成要素であるフェイス全体がなす束でも，対応する束の上下を反転すれば同じとなる双対性が成り立つ．したがって，双対性から半空間の交わりを求めることと，点集合の凸包を求めることとは，アルゴリズムの計算量の観点からは同じである．
+　以下，簡単のため2次元の場合を述べる．放物線<math>y=(x^2)/2\, </math>を用いれば，点<math>p=(p_x,p_y)\, </math>に対する極線<math>D(p)\, </math>は<math>y=p_xx-p_y\, </math>となる．<math>y\, </math>軸に平行でない直線<math>h\, </math>は，傾き<math>p_x\, </math>と<math>y\, </math>切片のマイナスの<math>p_y\, </math>を用いて<math>y=p_xx-p_y\, </math>と表せ，<math>h\, </math>の極<math>D(h)\, </math>は点<math>(p_x,p_y)\, </math>となる．<math>p\, </math>が放物線上にあるとき，<math>p\, </math>での接線が<math>D(p)\, </math>となる．
-次曲線として円を用いた場合の極変換も重要である．このとき，原点以外の点$(p_x,p_y)$は直線$p_xx+p_yy-1=0$に変換される．この直線は，原点からの距離が原点と元の点$(p_x,p_y)$の距離の逆数になっており，原点と元の点を結ぶ直線に垂直で，原点に関して元の点と同じ側の直線となる．
+　この変換は，接続関係(上下関係)を保存する．すなわち，点<math>p=(p_x,p_y)\, </math>と直線<math>h\colon y=q_xx-q_y\, </math>およびその双対変換<math>D(p)\colon y=p_xx-p_y\, </math>と<math>D(h)=(q_x,q_y)\, </math>に対して<math>p_y+q_y\, </math>と<math>p_xq_x\, </math>の大小関係に応じて以下のことが成立する．
-　円に関する極変換の変形に反転がある．反転は，原点以外の点$(p_x,p_y)$を上の極変換した直線への原点からの垂線の足に対応させる．反転により，原点を通る円は直線に変換される．この変換をもう1次元高い空間で行うと，球と平面の間の変換が得られる．たとえば、$(0,0,1)$を中心とする半径1の球面を基本となる二次曲面として採用した場合の極変換では，$xy$平面は$(0,0,1/2)$を中心とする半径$1/2$の球へ変換される．この変換は[[立体射影]] (stereographic projection) と呼ばれる．
+:(a) 点<math>p\, </math>が直線<math>h\, </math>上にあるとき，およびそのときのみ，点<math>D(h)\, </math>は直線<math>D(p)\, </math>上にある<math>(p_y+q_y=p_xq_x)\, </math>．
-　さらなる変形として，画像処理で特に用いられている[[ハフ変換]] (Hough transformation) がある．2次元の直線を原点からこの直線への垂線の距離$r$と直線と$x$軸がなす角度$\theta$で表して，それを
+:(b) 点<math>p\, </math>が直線<math>h\, </math>を境界とする上半平面(下半平面)にあるとき，およびそのときのみ，点<math>D(h)\, </math>は直線<math>D(p)\, </math>を境界とする上半平面(下半平面)にある．
-\mbox{直線}\, x\sin\theta+y\cos\theta=r \ \mapsto \mbox{点}\,(r,\theta)
+　接続関係(上下関係)の不変性は，2次曲線として円や楕円を用いて変換を定義しても成立し，一般の<math>d\, </math>次元空間でも成立する．点の集合はそれだけで扱うとばらばらで考えにくいため，アルゴリズム的にも上下関係など関係式がわかるように，この双対変換を適用して，直線(超平面)の集合からできる平面(空間)の交差図形を利用することがしばしば行われる．このとき，双対変換で1対1に対応するとともに，この関係式が保存され，直線(超平面)が交わって空間を分割することから問題がとらえやすくなる．このような直線(超平面)による平面(空間)の交差図形を[[アレンジメント]]と呼ぶ．アレンジメントの1つのセルに対応する[[凸多面体]]についても，ファセットを含む超平面で定まる半空間の交わりとしても，端点の凸包としても表せる．これは双対性の現れで，すべての次元の構成要素であるフェイス全体がなす束でも，対応する束の上下を反転すれば同じとなる双対性が成り立つ．したがって，双対性から半空間の交わりを求めることと，点集合の凸包を求めることとは，アルゴリズムの計算量の観点からは同じである．
+次曲線として円を用いた場合の極変換も重要である．このとき，原点以外の点<math>(p_x,p_y)\, </math>は直線<math>p_xx+p_yy-1=0\, </math>に変換される．この直線は，原点からの距離が原点と元の点<math>(p_x,p_y)\, </math>の距離の逆数になっており，原点と元の点を結ぶ直線に垂直で，原点に関して元の点と同じ側の直線となる．
+　円に関する極変換の変形に反転がある．反転は，原点以外の点<math>(p_x,p_y)\, </math>を上の極変換を施した直線への原点からの垂線の足に対応させる．反転により，原点を通る円は直線に変換される．この変換をもう1次元高い空間で行うと，球と平面の間の変換が得られる．たとえば、<math>(0,0,1)\, </math>を中心とする半径1の球面を基本となる二次曲面として採用した場合の極変換では，<math>xy\, </math>平面は<math>(0,0,1/2)\, </math>を中心とする半径<math>1/2\, </math>の球へ変換される．この変換は[[立体射影]] (stereographic projection) と呼ばれる．
+　さらなる変形として，画像処理で特に用いられている[[ハフ変換]] (Hough transformation) がある．2次元の直線を原点からこの直線への垂線の距離<math>r\, </math>と直線と<math>x\, </math>軸がなす角度<math>\theta\, </math>で表して，それを
+<center>
+直線　<math>x\sin\theta+y\cos\theta=r \ \mapsto\, </math>　点　<math>(r,\theta)\, </math>
+</center>
 と変換する．Hough変換は，画像からの直線成分やさらには楕円などを抽出することによく用いられる．
-　極変換は2次曲線を核としていたが，核を一般の凸関数に拡張することもできる．この場合の双対変換は，Legendre変換と一般に呼ばれ，特に最適化の分野ではFenchelの共役性として知られている．この場合，核の凸関数の共役凸関数が定義でき，放物線$y=(x^2)/2$は自己共役になっている．凸関数の共役性は，凸解析の基本概念である．
+　極変換は2次曲線を核としていたが，核を一般の凸関数に拡張することもできる．この場合の双対変換は，Legendre変換と一般に呼ばれ，特に最適化の分野ではFenchelの共役性として知られている．この場合，核の凸関数の共役凸関数が定義でき，放物線<math>y=(x^2)/2\, </math>は自己共役になっている．凸関数の共役性は，凸解析の基本概念である．
 ----
 '''参考文献'''
-[1] H. Edelsbrunner, ''Algorithms in Combinatorial Geometry,'' Springer-Verlag,
+[1] H. Edelsbrunner, ''Algorithms in Combinatorial Geometry,'' Springer-Verlag, 1987.　邦訳(今井浩, 今井桂子訳), 『組合せ幾何学のアルゴリズム』，共立出版, 1995.
-.　邦訳(今井浩, 今井桂子訳), 『組合せ幾何学のアルゴリズム』，共立出版, 1995.
 [2] F. P. Preparata and M. I. Shamos, ''Computational Geometry: An Introduction,'' Springer-Verlag, 1985. 邦訳 (浅野孝夫, 浅野哲夫訳) , 『計算幾何学入門』, 総研出版, 1992.
 [3] 佐々木建昭, 今井浩, 浅野孝夫, 杉原厚吉, 『計算代数と計算幾何』, 岩波応用数学[方法9], 岩波書店, 1993.
+[[Category:計算幾何|そうついへんかん]]

「《双対変換》」の版間の差分

2007年8月7日 (火) 02:15時点における最新版

案内メニュー

検索