《ロバスト化技術》のソースを表示

'''【ろばすとかぎじゅつ (design of robust algorithms) 】'''

　幾何アルゴリズム理論は, 無限精度で計算ができるという前提のもとで発展してきたため, 有限精度の計算しかできない現実のコンピュータでそのまま走らせても正常に動作するとは限らない. 誤差のために対象の位置関係の判定を誤ると, 矛盾が生じてアルゴリズムが破綻してしまう. このように数値的に不安定なアルゴリズムを, 有限精度で計算を行っても破綻しないソフトウェアへ改良する技術は, [[ロバスト化技術]] (design of robust algorithms) とよばれる. 

　代表的なロバスト化技術の一つは, 対象の位置関係の判定を正確に行えるだけの十分高い精度の計算を用いる方法である. これは[[厳密計算法]] (exact arithmetic method) とよばれる. 点の座標を始めとする幾何データはそもそも有限の精度でコンピュータに与えられる. したがって, それに有限回の四則演算を施した結果も離散的な値しかとりえない. 幾何的位置関係は, そのような計算結果の符号によって判定されるから, 正確な判定に必要な計算精度も有限ですむ. これが厳密計算法の原理である [1, 2]. 

　たとえば 2 次元平面内の点 ${\rm P}_i \; (i=1,2, \cdots)$ の座標 $(x_i,y_i)$が $k$ ビットの整数で与えられた場面で, 点 ${\rm P}_{2i-1}$と点 ${\rm P}_{2i}$ を通る 3直線 $(i=1,2,3)$ が同一の点で交わるか否かを判定したいとする. 通常の整数の表現は絶対値に $k-1$ ビット, 符号に 1 ビットを使っているとみなすことができるので


$$|x_i|, |y_i| \leq 2^{k-1}-1 \quad (i=1,2, \cdots )$$


である. 一方, 3 直線が 1 点で交わるための必要十分条件は, 3 本の直線を表す方程式の係数行列の行列式


F=\left| \begin{array}{ccc}
y_2-y_1 & x_1-x_2 & x_2y_1-x_1y_2\\
y_4-y_3 & x_3-x_4 & x_4y_3-x_3y_4\\
y_6-y_5 & x_5-x_6 & x_6y_5-x_5y_6 \end{array} \right|


が 0 となることである. アダマールの不等式(行列式の絶対値は, その行列の列ベクトルの大きさの積より大きくない)より


F < (\sqrt{3}\cdot 2^k) (\sqrt{3}\cdot 2^k) (\sqrt{3}\cdot 2^{2k-1}) =3\sqrt{3}2^{4k-1}< 2^{4k+2}-1


である (上の不等式は, たとえば第 1 列ベクトルの大きさは


\sqrt{(y_2-y_1)^2+(y_4-y_3)^2+(y_6-y_5)^2}\leq \sqrt{3 \cdot 2^{2k}}=\sqrt{3}\cdot 2^k


であることなどから導ける). したがって $4k+3$ ビットの長さの整数表現を用いて $F$ を計算すれば正しく値が計算でき, その符号も正しく判定できる. このように厳密計算法では, おのおのの計算式に対して, その符号を正しく知るために必要な精度の上限を見積り, その精度を確保した上で判定のための計算を行なう. これによって, 矛盾の発生を防ぐことができる. 

　厳密計算法では位置関係が厳密に判定できるために三角形の 3 頂点が一直線上に並ぶなどの退化した状況も厳密にわかる. したがって, それぞれの退化に対する例外処理を整備しないとアルゴリズムは完成しない. しかし, 例外処理のためのソフトウェア作りは苦痛の多い作業である. これを回避するための自動退化解消法が[[記号摂動]] (symbolic perturbation) とよばれる技術である. 幾何アルゴリズムの入力データとなる座標値などの数値は整数環あるいは有理数体の要素とみなせる. ここに無限小を表す記号 $\varepsilon$を導入し, 入力データに $\varepsilon$ の多項式を加えることによって, 入力データに無限小の摂動を与える. このようにして数値の世界を$\varepsilon$ の多項式の世界へ拡張し, この多項式の世界で計算と符号判定を行なう. このとき, 入力データに与える摂動の大きさを工夫すると計算結果が決して 0 にならないようにすることができる. 退化とは正か負かを判定すべき値が 0 になることであるから, この摂動によって退化の生じない世界を自動的に作ることができる. 記号摂動を用いると, 例外は生じないものと仮定してソフトウェア作りができ, しかもでき上がったソフトウェアは退化した入力に対しても正常に動作する. 詳しくは文献 [1, 3] などを参照されたい. 

　もう一つの代表的なロバスト化技術に[[位相優先法]] (topology-oriented method) がある. これは, 厳密計算法とは逆に数値計算結果はもともと誤差を含むものであるという前提に立って, 対象の位相的構造の一貫性を保つことを数値計算結果より優先順位の高い情報とみなすことによって, 位相的矛盾の発生を防ぐ方法である. この方法は, 通常の浮動小数点計算が利用できるため処理速度が速いうえに, 例外処理がいらないという利点をもつ. ただし, 厳密計算法ほどその適用方法は機械的ではない. 扱う幾何的対象がもつべき位相的性質を抽出してそれを利用するから, 扱う問題ごとの個別の工夫が必要である. 厳密計算法は初心者用技術, 位相優先法は中級者向け技術といえよう. この手法の詳細は文献 [1] などを参照されたい. 



----

'''参考文献'''

[1] 杉原厚吉, 『計算幾何工学』, 培風館, 1994.

[2] C. Yap and T. Dub&eacute;, "The Exact Computation Paradigm," in ''Computing in Euclidean Geometry, Second Edition'', D.-Z. Du and F. Hwang, eds., World Scientific, Singapore, 452-492, 1995.

[3] H. Edelsbrunner and E. P. M&uuml;cke, "Simulation of Simplicity -A Technique to Cope with Degenerate Cases in Geometric Algorithms," in ''Proceedings of the 4th Annual Symposium on Computational Geometry'', Urbana-Champaign, Illinois, 118-133, 1988.