読者です 読者をやめる 読者になる 読者になる

凸包と記号摂動法

 

参考文献

図書館でたまたま目に入ったというだけの理由で計算幾何学の本を読みました。この本は説明のわかりやすさもさることながら、文章がうまくて読んでいて楽しかったです。

本の最初に乗っていたアルゴリズムを実装したので解説してみます。コードはgithubにあります。

考える問題は二次元平面上の点の集合\(X\)を入力として、\(X\)の凸法を求める問題です。

逐次追加法

この問題を解く逐次追加法と呼ばれるアルゴリズムがあります。\(x\)座標が小さい順に考慮する点を増やし、各段階で\((x_1, \cdots, x_i)\)に対する凸包\(Y\)を作る、という名前の通りのアルゴリズムです。

入力: 点の集合\(X\)

出力:\(X\)の凸包\(Y\)

アルゴリズム :

  1. \(X\)\(x\)座標で昇順にソートし、ソート結果を\((x_1, \cdots, x_n)\)とする。
  2. \(x_1, x_2, x_3\)を左回りになるように並べたものを\(Y\)とする。
  3. \(i=4\)とする。
  4. \(x_p\)を、「\(x_i\)から見える\(X\)の点の中で一番右にある点」とする。
  5. \(x_q\)を、「\(x_i\)から見える\(X\)の点の中で一番左にある点」とする。
  6. \(Y\)に属する点で、\(x_p\)\(x_q\)の間にあるものを\(Y\)から削除する。
  7. \(Y\)\(x_p\)の直後に\(x_i\)を追加する。
  8. \(i = n\)なら\(Y\)を出力して終了。
  9. \(i = i + 1\)として、\(4\)に戻る。

ただし、点の集合\(X\)\(X\)の外部の点\(p\)に対して、

 \(x \in X\)\(p\)から見える\(\Leftrightarrow\)\(p\)\(x\)を結ぶ直線が\(X\)の内部を通らない

とする。

逐次追加法のステップ3, 4では、点の集合の中で一番右端(あるいは左端)にある点を調べるのに以下の関係を使います。

\[F(a,b,c)=\left| \begin{array}{ccc} 1 & a_x & a_y \\ 1 & b_x & b_y \\ 1 & c_x & c_y \end{array} \right|\] について、

\(F(a,b,c) \gt 0\)ならば3点\((a, b, c)\)がこの順番に左に折れている。

\(F(a,b,c) \lt 0\)ならば3点\((a, b, c)\)がこの順番に右に折れている。

退化

逐次追加法は\(X\)の点が常識的に位置している場合には正しい凸包を計算できますが、例外的な場合には計算に失敗することがあります。

例外的な場合とは、ステップ4,5で\(F(p,q,r)=0\)となる場合です。これは3点が一直線上にある、または3点の座標が全く同じ場合に相当します。このような、一般的な方法で解くことができない例外的な(たちの悪い)状態を「退化」といいます。

退化なんて例外的なんだからほっておいてもいいだろうと考えたくなりますが、そういうわけにも行きません。なぜなら、コンピュータで扱う数値は有限の精度しか持たない以上一致することはあり得るうえに、退化が起きた結果正しい答えとまるっきり違った解答をしてしまう可能性があるためです。もしこれがソートの問題なら、退化が起きたとしても問題にはならなかったでしょう(同じ数値の点はどう並べても良いため)。

記号摂動法

退化の問題を解決する方法の一つが記号摂動法です。記号摂動法の考え方は、座標が全く同じだとまずいのだから、すべての点を微小量ずつランダムにずらして同じ値を持つ点をなくしてしまえば良い、というものです。微小量ずらすと言っても本当に値をずらしてしまうとずらさずにうまく行っていた処理がうまくいかなくなる可能性があるので、値をずらすことはせずに、微小量は多項式の項として追加するという方法を取ります。

具体的な手順は以下のようになります。

入力された点の集合\[X=\{(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)\}\] に対し、十分大きな整数\(M\)を用いて\(\varepsilon\)多項式\(x'_i, y'_i\)\((i = 1, \cdots, n)\)\[(x'_i, y'_i) =(x_i+\varepsilon^i, y_i + \varepsilon^{Mi})\] と定義する。そして \[X'=\{(x'_1, y'_1), (x'_2,y'_2), \cdots, (x'_n, y'_n)\}\] についてアルゴリズムを適用する。 ただし、\(\varepsilon\)多項式の符号は、多項式\(0\)で無い項のうち一番次数の小さなものの符号とする。

このようにすることで、\(F(a, b, c)\)の符号の計算について以下のような性質が成り立ちます。

  • 記号摂動を使えば退化は起きない。
    • 退化が起こるとき\(F(a, b, c)\)\(\varepsilon\)多項式として\(0\)となるが、\(a_x,a_y,b_x,b_y,c_x,c_y\)は全て違う\(\varepsilon\)の次数を持つことからそのようなことは起こり得ない。
  • 記号摂動を使わないでも退化が生じていない場合、記号摂動を用いても同じ結果が得られる。
    • 退化が生じていない場合には\(F(a, b, c)\)の符号が定数項の符号で判定されるため。
  • 記号摂動を使わないと退化が生じる場合、記号摂動によって\(F(a, b, c)\)の符号が一意に定まり、かつ幾何学的な性質を満たす。
    • 全ての\(i\)について\(x'_i\)\(y'_i\)に順序が定まっているため。

このような性質によって、退化を場合分けに頼ることなく一気に解決することができます。

おまけ: ギフトラッピング法

凸法を求めるアルゴリズムは逐次追加法の他にもギフトラッピング法と呼ばれるアルゴリズムがあります。

\(X\)の中で一番右端にある点に紐の片方の端をくくりつけ、紐のもう片方の端を持って左回りに回していったときに紐が触れる点と同じ順番で\(Y\)に点が追加されていきます。3次元で同じことをやると箱を包装紙で包むやり方に似るのでギフトラッピング法と名づけられたのでしょう。

入力: 点の集合\(X\)

出力:\(X\)の凸包\(Y\)

アルゴリズム :

  1. \(X\)の中で\(x\)座標が一番大きいものを\(p\)とする。
  2. \(p_{1}=p\)とする。
  3. \(q\)を、「\(X-\{p\}\)に属する点\(q\)のうち、\(\vec{pq}\)\(y\)軸正方向のなす角度が最小になる点」とする。
  4. \(Y = \{ \vec{pq} \}\)とする。
  5. \(U = X\)とする。
  6. \(r\)を、「\(U\)に属する点\(r\)のうち、\(\vec{pq}\)\(\vec{q r}\)のなす角度が最小になる点」とする。
  7. \(Y\)\(\vec{q r}\)を追加する。
  8. \(r\)\(p_1\)だったら、\(Y\)を出力して終了。
  9. そうでなかったら、\((p,q) = (q,r)\)として6.に戻る。

このアルゴリズムのステップ6では3点の関係を調べるのに以下の関係を使います。

平面上の\(3\)\(p, q, r\)について、\(\vec{pq}\)\(\vec{q r}\)のなす角度を\(\theta\)とすると \[cos\theta = \frac{\vec{pq} \cdot \vec{q r}}{|\vec{pq}||\vec{q r}|}\]

ステップ6では\(\vec{pq}\)が凸包の辺であることから\(0 \le \theta \le \pi\)であり、かつこの範囲において\(cos\theta\)は単調減少なことから、\(\theta\)の最小値を求めるには\(cos\theta\)の最大値を求めればいいことがわかります。

\(p=q\)または\(q=r\)のとき\(cos\theta=\infty\)となるため、このアルゴリズムでも退化が起きます。しかしこの退化は逐次追加法で起こった退化よりたちが悪いです。\(cos\theta\)は割り算を含むので、記号摂動法では計算できないためです。

この退化の解決法は本に載っておらず、また自分で思いつくこともできなかったので書けませんが、単純で簡単なアルゴリズムが常に最良であるわけではないという例だと思ったので書きました。