技術要約：点と楕円の距離に関する保証付き区間法

1. 問題設定

点 $P=(x_0, y_0)$ から楕円 $E: x^2/a^2 + y^2/b^2 = 1$ へのユークリッド距離 $d^*$ の計算は、衝突検知、ロボティクス、およびCAD/CAMの公差設計において用いられる基本的な幾何学的プリミティブである。その定式化は極めて単純であるにもかかわらず、この問題は浮動小数点演算において堅牢に解くことが非常に困難であることで知られている。

角度 $\theta$ によってパラメータ化された二乗距離関数 $d^2(\theta)$ は、最大4つの臨界点を有する。点 $P$ が楕円の進化曲線（アストロイド）に対してどのような位置にあるかに応じて、局所最小値が1つまたは2つ存在する可能性がある。標準的な数値解法（勾配降下法、黄金分割探索、または単一シードのニュートン反復など）は、しばしば大域的最小値ではなく局所的最小値に収束したり、以下のような退化した構成において完全に失敗したりする：

• 楕円の軸や焦点の近くにある点。
• 進化曲線の近くにある点（接合構成）。
• 遠方のクエリにおける「極」（$\theta = \pi$）付近の点。
• 円の極限（$a=b$）および極端に平坦な楕円（$a/b \gg 1$）。

既存の代数的手法（ラグランジュの未定乗数法など）は、偽の根を導入したり、これらの退化したケースにおいて悪条件（ill-conditioning）に陥ったりすることが多い。さらに、一般的な区間分枝限定法（interval branch-and-bound）は、厳密ではあるものの、問題の四次性の構造的活用に欠けることが多く、平坦な最小値を持つシナリオにおいて計算の深さが過剰になる傾向がある。

本論文は、浮動小数点の丸め誤差や入力の特定の構成に関わらず、真の距離 $d^*$ を確実に含む区間 $[d_{lo}, d_{hi}]$ を返す保証付きアルゴリズムの必要性に対処するものである。

2. 手法

提案手法である CertP2E は、二重パラメータ化戦略、微分単調性に基づく厳密な根の孤立フレームワーク、および「距離の保証原理（Certified Distance Principle）」による、距離の保証と根の存在証明の分離という3つの核心的な柱に基づいている。

2.1 数学的定式化

二乗距離の臨界点は、半角置換 $u = \tan(\theta/2)$ を通じて導かれる四次方程式 $S(u)$ の根である：
$$S(u) = by_0 u^4 + 2(a^2 - b^2 + ax_0)u^3 - 2(a^2 - b^2 - ax_0)u - by_0 = 0$$
本論文は、$S(u)$ の判別式と楕円の進化曲線（アストロイド）の暗黙方程式との間の正確な関係を確立している。この恒等式は、$P$ が進化曲線上に存在する場合に限り $S(u)$ が重根を持つことを証明しており、また、$P$ がアストロイドの外側、上、または内側にあるかに基づいて、実数臨界点の数（2、3、または4）を分類する。

2.2 二重パラメータ化

単一のチャート（$u = \tan(\theta/2)$）は、極 $\theta = \pi$ （遠方の点）付近の点において、根が悪条件（$\kappa \sim 10^{15}$）となるため機能しない。これを解決するために、アルゴリズムは二重チャートアプローチを採用する：

1. $u$-チャート: $u = \tan(\theta/2)$。範囲 $|u| \le T$（ここで $T=10^2$）をカバーする。
2. $w$-チャート: $w = \tan((\pi-\theta)/2) = 1/u$。範囲 $|w| \le 1/T$ をカバーする。

主要な定理（定理 5.5）は、条件付けの恒等式 $\hat{\kappa}_w(w^*) = \hat{\kappa}_u(u^*) / u^{*2}$ を証明している。これにより、任意の単純な臨界点は、少なくとも一方のチャートにおいて良好な条件付け（well-conditioned）を持つことが保証される。一方のチャートで悪条件となった根は、もう一方のチャートでは極めて小さな、良好な条件付けを持つ根となる。

2.3 シードフリーの根の孤立

本アルゴリズムは、ヒューリスティックな「シード」に依存することなく根を孤立させる。代わりに、導関数 $S'(u)$ の単調性に基づいてドメインを分割する。

• ドメインは $S''(u)$ および $S'(u)$ の根で分割される。
• 各部分区間において、アルゴリズムは $S'(u)$ が一定の符号を維持しているかを確認する（単調性を証明するため）。
• 根が存在しないことが証明された区間は破棄される。そうでなければ、区間ニュートンステップまたは二分法を用いて処理される。
• 飽和受理（Saturation Acceptance）: 退化した構成（例：$S(u)$ が三重根を持つアストロイドの尖点）の近くでは、導関数が消失し、標準的なニュートン法が停滞する。アルゴリズムは、ボックス幅の「飽和受理」閾値（$10^{-10}$）を採用する。これらのボックスを終端として受け入れ、これらの点における $d^2$ の値の平坦性が、結果としての距離誤差が無視できる程度（$O(h^4)$）であることを保証していることに依拠する。

2.4 距離の保証原理 (CDP)

最も重要な理論的貢献は、距離の保証原理（定理 3.8）である。従来の検証付き根の孤立は、すべての終端ボックスに根が含まれることを証明する必要があった。CDPは、この要件を緩和する：

• $d^*$ を保証するためには、すべての孤立したボックスに根が含まれることを証明する必要はない。
• 以下の条件を満たせば十分である：
  1. 大域的最小値を含むボックスがフィルタチェーンを生き残ること（網羅的なブラケティングによって保証される）。
  2. すべての区間評価が外向きに丸められている（outwardly rounded）こと。
  3. 上界 $U$ が厳密に維持されていること。
• したがって、生存しているすべてのボックスにおける $[\min_I d^2(I), \min_I d^2(I)]$ は、たとえ一部のボックスが「未証明」（すなわち、その根の存在が形式的に検証されていない）であったとしても、$d^{*2}$ を確実に含む。これにより、アルゴリズムは、根の証明が不可能になる退化したケースにおいても、健全性を損なうことなく扱うことができる。

3. 主な貢献

1. 距離の保証原理: 距離の証明と根の存在証明を分離する健全なフレームワークを提供し、退化した構成において根の証明が失敗しても、アルゴリズムが厳密性を維持できるようにした。
2. 二重チャートによる条件付け: $u$ チャートと $w$ チャートの組み合わせにより、すべての単純な臨界点が少なくとも一方のチャートで良好な条件付けを持つことを保証し、単一チャート手法における「極のギャップ」による失敗モードを排除した。
3. シードフリーの網羅的ブラケティング: 導関数の単調性に基づく決定論的な分割戦略により、ヒューリスティックなシードに頼ることなく、すべての臨界点を網羅することを保証する。
4. 退化の処理: 値の平坦性推定（value-flatness estimates）と飽和受理を用いることで、接合、アストロイドの尖点、円の極限、および平坦な楕円を統一的に扱い、これらが計算複雑度の爆発を引き起こさないようにした。

4. 実験結果

アルゴリズムは、50桁の可変精度オラクルを用いた包括的なテストバッテリーに対して検証された：

• 372ポイントのバッテリー: 文献にある既知の失敗ケース、正確な接合、アストロイドの尖点、および極端なアスペクト比（$a/b$ が $10^6$ まで）を含む。
• 敵対的ファミリ: 均一、軸付近、進化曲線付近、中心付近、平坦、および遠方点の設定をカバーする、それぞれ $10^5$ 点からなる6つのファミリ。
• 比較: 代数的な閉形式、幾何学的列挙、単一シード・ニュートン、および一般的な区間分枝限定法と比較した。

結果:

• 正確性: 約 $10^6$ クエリのすべてにおいて、認証された区間がオラクル距離を包含していた（100%）。オラクル違反は観察されなかった。
• 精度: 認証された区間の中央相対幅は、マシン精度レベル（$\sim 10^{-14}$）であった。
• 堅牢性: ベースライン手法（ファミリに応じて14～100%で失敗）とは異なり、CertP2Eは「致命的な誤り」を出力しなかった。
• 性能: 標準的なノートPCでの平均クエリ時間は約 15 ms であった。非厳密なベースライン（1 ms 未満で動作）よりは遅いが、退化した入力に対する一般的な区間分枝限定法よりも数桁高速である。
• 退化ケース: 単一チャート手法が、無制限または誤った結果を返していた構成（軸上の点、極付近、正確な尖点など）を、本アルゴリズムは正常に処理し、タイトな区間を返した。

5. 意義と主張

本論文は、CertP2Eが、あらゆる幾何学的構成に対して堅牢であり、かつ実用的なエンジニアリング用途（例：CADのクリアランス検証）に適した計算効率を備えた、最初の厳密に保証された点と楕円の距離解法であることを主張している。

その意義は、「近似的な距離を見つける」ことから「保証された区間を提供する」ことへの転換にある。著者は以下を強調している：

• 距離の保証原理は、退化したケースにおいて根の存在証明に伴う過大なコストを課すことなく、厳密な境界を計算することを可能にする根本的な洞察である。
• 二重パラメータ化は、特に遠方の点や極付近の最小化問題において、従来の数値的アプローチを悩ませてきた条件付けの問題を解決する。
• 本手法は**完全（complete）**である：ヒープリステックに依存して大域的最小値を逃す可能性がない。

結論として、計算コストは非厳密な手法よりも高くなるものの、健全性の保証は、静かな失敗（誤った距離の算出）が許されない衝突回避や公差分析のような安全性が重視されるアプリケーションにおいて不可欠である。本手法は、3Dの楕円体や一般的な二次曲面へ拡張可能な平面解として提示されている。