堅牢な幾何学計算

数学、特に計算幾何学において、幾何学的非堅牢性は、計算幾何学アルゴリズムの分岐決定が近似数値計算に基づいているために、不正な出力やクラッシュや無限ループによるソフトウェア障害など、さまざまな形の信頼性の欠如につながる問題です。

たとえば、凸包の構築などの問題のアルゴリズムは、特定の「数値述語」の値が正、負、またはゼロであるかどうかをテストすることに依存しています。不正確な浮動小数点計算によって、ゼロに近い値が正確な値とは異なる符号を持つ場合、結果として生じる不一致がアルゴリズム全体に伝播し、正しい出力とはかけ離れた出力が生成されたり、クラッシュしたりする可能性があります。

この問題を回避する方法の 1 つは、アルゴリズムによって表されるすべての座標およびその他の量に浮動小数点数ではなく整数を使用し、整数オーバーフロー状態を回避するためにすべての計算に必要な精度を決定することです。たとえば、2 次元の凸包は、2 次多項式の符号をテストする述語を使用して計算できるため、これらの計算では入力数の 2 倍のビットの精度が必要になる場合があります。整数演算を使用できない場合 (たとえば、計算の結果が整数または有理数ではなく代数的数である場合)、2 番目の方法は、記号代数を使用して、すべての計算を数値近似値ではなく正確に表現された代数的数で実行することです。 3 番目の方法は、「浮動小数点フィルター」と呼ばれることもあり、最初に浮動小数点演算に基づく不正確な方法を使用して数値述語を計算しますが、結果の精度の境界を維持し、これらの境界によって計算された値がゼロと分離されない場合に、より遅い記号代数法を使用するか、数値的に追加の精度を使用して計算を繰り返す方法です。

• Mei, Gang; Tipper, John C.; Xu, Nengxiong (2014)、「幾何学計算における数値的堅牢性：解説的要約」、応用数学および情報科学、8 (6): 2717–2727、doi :10.12785/amis/080607、MR  3228669、S2CID  54807426
• Sharma, Vikram; Yap, Chee K. (2017)、「堅牢な幾何学計算」(PDF)、Goodman, Jacob E.、O'Rourke, Joseph、Tóth, Csaba D. (編)、離散幾何学と計算幾何学ハンドブック、CRC Press 離散数学とその応用シリーズ (第 3 版)、CRC Press、pp. 1189–1223、MR  1730191
• シェウチュク、ジョナサン(2013 年 4 月 15 日)、幾何学的ロバスト性に関する講義ノート(PDF)