《双対変換》

出典: ORWiki

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

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

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


a_1x_1+a_2x_2+\cdots+a_dx_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_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\,の大小関係に応じて以下のことが成立する．

(a) 点p\,が直線h\,上にあるとき，およびそのときのみ，点D(h)\,は直線D(p)\,上にある(p_y+q_y=p_xq_x)\,．
(b) 点p\,が直線h\,を境界とする上半平面(下半平面)にあるとき，およびそのときのみ，点D(h)\,は直線D(p)\,を境界とする上半平面(下半平面)にある．

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

　2次曲線として円を用いた場合の極変換も重要である．このとき，原点以外の点(p_x,p_y)\,は直線p_xx+p_yy-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.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E5%8F%8C%E5%AF%BE%E5%A4%89%E6%8F%9B%E3%80%8B" より作成