双対変換

説明

二次元平面上の点 p は二つのパラメタ (x,y) で指定される．一方，y 軸と垂直でない二次元平面上の直線 l も二つのパラメタ (a,b) （傾きと切片）で指定される．（幾何学的）双対変換とは，点と直線の間の全単写で，いくつかの良い性質を持つものをいう．

双対変換はいくつも存在するが，特に有用な双対変換として「点 (a,b) に対して直線 { (x,y) | y = a x - b } を対応させる」変換がある．特に断らずに双対変換と言った場合は，この双対変換を指すものとし，点 p の双対変換を p*，直線 l の双対変換を l* であらわす．この変換の代表的な性質として次の三つが挙げられる．

• 反射性：p** = p, l** = l．
• 距離の保存：点 p と直線 l の最短距離 d(p,l) と点 l* と直線 p* の最短距離 d(l*,p*) は等しい．
• 順序の保存：点 p が直線 l の左/上/右にあることと，点 l* が直線 p* の左/上/右にあることは同値．

双対変換は言葉の言い換えでしかないので，直接アルゴリズムとして用いて有益になる，ということは少ない．しかし，言葉の言い換えであるという点が重要である．どう解いたらよいかわからないような問題に対して双対変換を施すことによって，問題の解き方が分かることがある．それを再度双対変換することで，元の問題の解き方が得られる．

双対変換を用いることによって，解き方が見やすくなる問題の例を以下に示す．

1.

Ham-Sandwich Problem．二種類の点の集合 R, B が与えられる．R の点と B の点を，同時に二等分割する直線 l を求めよ．

異なる直線であっても同じ点の分割を与えることがあるので「すべての直線を調べる」と考えるのは，難しい．そこで問題を双対変換すると，次の問題が得られる．

Dual Ham-Sandwich Problem．二種類の直線の集合 R*, B* が与えられる．次の条件を満たす点 l* を求めよ．R* の線の半分が l* の上，もう半分が l* の下．かつ B* の線の半分が l* の上，もう半分が l* の下．

直線で切られた各領域内では，点と直線たちの上下関係は変化しないので，すべての領域を探索すればよい．これは O(n^2) 個存在する．これらの領域をうまく走査することで，O(n^2) のアルゴリズムが得られる．

2.

Stabbing Line Problem．線分の集合が与えられる．それらをすべて貫く直線 l を求めよ．

これも，異なる直線であっても同じ貫き方をすることがありうる．そこで双対変換を施す．線分は点の集合なので，それを双対変換すると直線の集合（一点で交わる直線の集合：くさび形）となる．したがって線分と直線が交わる，という状況は，双対空間では，くさび形の中に点が入る，という状況になる．したがってこの問題の双対問題は次のようになる．

Dual Stabbing Line Problem (Wedges Intersection Problem)．くさび形の集合が与えられる．これらの共通部分を求めよ．

n 個のくさび形の共通部分は O(n) 個の頂点を持ち，それと新たなくさび形との共通部分を求めるのは O(n) でできるので，計算量は O(n^2) となる．

ソースコード

// point p = (a,b)  <---> line l = { (x,y) | y = a x - b }
line dual(const point &p) {
  return line( point(0, -imag(p)), point(1, real(p) - imag(p)) );
}
point dual(const line &l) {
  const point &p = l[0], &q = l[1];
  return point( imag(p-q)/real(p-q), cross(p,q)/real(q-p) );
}