巨大証明から 1 ページまで：幾何学的ランランド予想とポアソン・ディスク分布

数学の世界における対照的な成果

• 2024 年の巨大な証明
  • 9 人の数学者チームが、**幾何学的ランランド予想（geometric Langlands conjecture）**に関する約 1,000 ページに及ぶ論文を発表。
  • 純粋数学の傑出した成果であり、証明全体像を理解することは極めて困難である。
• 2007 年の簡潔な解決策
  • ロバート・ブリッドソン（Robert Bridson）氏が1 ページの論文で問題を解決。
  • ほぼ 1,000 引用を受け、理解に要する時間は10 分未満。
  • コンピュータグラフィックスやシミュレーションにおける「ランダムかつ互いに近すぎない配置」への単純かつ強力な解決策を提供。

---

ブリッドソンのアルゴリズム：基本手順

点同士の最小距離を $r$、空間の次元を $d$ とする場合、以下の手順でポアソン・ディスク分布を実現する。

1. グリッド分割
   • 側辺長が $\frac{r}{\sqrt{d}}$ のグリッドに空間を分割し、各セル内の点は最多 1 つだけあるようにする。
2. 初期化

   • active

     リストを空にし、空間から一様ランダムに選んだ点を格納する。
3. ループ処理（

   active

   が空になるまで）

   • active

     から均等にランダムな要素 $p$ を選択。
   • サンプリング試行：$p$ を中心とする内半径 $r$、外半径 $2r$ の環状領域（annulus）について、最多 $k$ 回一様サンプリングを試みる。
     • 成功時：有効なサンプルを見つけた場合、グリッドを効率よく用いて衝突検出を行い、その点を

       active

       に追加して新たな $p$ を選択。
     • 失敗時：$k$ 回の試行でも見つからない場合、$p$ を

       active

       から削除。

• 推奨設定：ブリッドソン氏は $k = 30$ を推奨している。

環状領域の一様サンプリング方法

最も簡単な実装方法は以下の通りです。

$$ \text{sample} = r x^{1/d} \cdot \vec{v} $$

• $\vec{v}$：$\mathbb{R}^d$ における単位ベクトル。
• $x$：区間 $[\frac{1}{2^d}, 1)$ から一様ランダムに選んだ数。
• 二次元の場合：単位ベクトルを選ぶことは角度 $\theta \in [0, 2\pi)$ を選ぶことと同等。
• 高次元の場合：各成分を正規分布からサンプリングしたベクトルを規格化する。

---

ブリッドソンアルゴリズムの改善案

1. 親子最適化（Parent Optimization）

二次元での有効性が確認された改良法。点 $q$ を配置した後、その「親（parent）」である点 $p$ との距離関係を利用してサンプリング範囲を狭めます。

• 原理：親点 $p$ と子点 $q$ の間には一定の制約があるため、環状領域の一部（角度 $\alpha + 2\beta$）は無効となります。この錐（cone）の外側のみからサンプリングします。
• 角度計算： $$ \begin{align*} \alpha &= \operatorname{atan2}(p_y - q_y, p_x - q_x) \ \beta &= \min\left(\arccos\frac{|p-q|^2+3r^2}{4r \cdot |p-q|}, \arccos\frac{|p-q|}{2r}\right) \end{align*} $$
  • 注意点：

    min

    演算子は、錐の境界が環状領域の内円か外円かで変わるため必要です。点距離が $\sqrt{3} \cdot r$ を超えると交点の決定因子が変わります。
• 実装コスト：各点に対して単に親点を記憶しておけば実現可能。

2. 距離分布制御（Distance Distribution Control）

サンプリングする「角度」を変えるのではなく、「中心からの距離」の分布を変更します。これにより密度調整が可能です。

• 累積分布関数（CDF）の変更： $$ F_c(x) = \begin{cases} 0 & x \leq r \ \frac{x^c - r^c}{(2^c - 1)r^c} & r < x \leq 2r \ 1 & x > 2r \end{cases} $$

  • $c=2$ の場合が元の一様分布に相当します。

• $c=0$ の定義（ゼロ除算回避）： $$ F_0(x) = \begin{cases} 0 & x \leq r \ \log_2{x} - \log_2{r} & r < x \leq 2r \ 1 & x > 2r \end{cases} $$

• 逆変換サンプリングによる実装：

  • $c=0$ の場合：半径は $r \cdot 2^x$（$x \in [0, 1)$）。
  • それ以外の場合：$y \in [\frac{1}{2^c}, 1]$ から一様選択し、半径を $r y^{1/c}$ とする。

最適化パラメータの実践的設定

• 高次元への適用：環状領域の体積効果は無視できやすいため効果は低下します。
• バランスの重要性：密度最大化だけでは分布が「ランダムに見えない」ため、適度な一様性が重要です。
• 経験則による最適解：
  • 固定範囲 $15 \leq k \leq 40$ の場合、以下の式が最も効果的とされます。 $$ c = -1.4 - \frac{17}{\sqrt{k}} $$
  • この設定では生成点数が飽和被覆率（約 54.7%）に近くなり、ランダム性と一様性のバランスが取れます。

---

応用：スタッピン（Stippling）効果

半径 $r$ を固定する必要はなく、位置に応じて動的に変化させることができます。

• 実装方法：点 $p$ の配置後に、内半径 $r(p)$ の環状領域をサンプリングします。
• 画像処理への応用：
  • 画像の各ピクセルの明るさを $r$ として定義することで、スタッピン（ドット描画）効果を実現可能。
  • カラーチャンネルごとに独立したポアソン・ディスクサンプルを組み合わせることも可能です。

---

スケーラビリティと並列化

• 順次処理 vs 並列処理：ブリッドソンのアルゴリズムは本質的にシークエンシャルですが、並列化された実装（PixelPie など）で大幅なパフォーマンス向上が図れます。
• Poisson Cam：リアルタイムビデオスタッピンツールとして、Rust とシェーダープログラミングを用いて開発されました。

---

スコット・A・ミッチェル氏の手法（2022 年）

階層的なダーツ投げ込み法とは異なる、拒絶サンプリングを回避する新しいアプローチです。

3 つの特徴

1. 最大化性（Maximality）：終了時点では、ポアソン・ディスク性質を保ちながらさらに点を追加できないことが保証されます。
2. 一様性（Uniformity）：すべての最大サイズセットに対して一様分布サンプリングを行います。
3. 決定論的性質（Determinism）：拒絶サンプリングや「配置失敗」の概念がありません。

パフォーマンスと実装の難易度

• 速度：最適化されたブリッドソンアルゴリズム（親子最適化、$k=20, c=-5.2$）と比較しても同等の速度で動作。
• 生成点数：ほぼ同じ出力量を確保します。
• 欠点：実装の複雑さが著しく高いことが唯一のデメリットです。

簡略化されたアルゴリズム概要

1. 空間を側辺長 $\frac{r}{\sqrt{d}}$ のグリッドに分割。
2. 点が追加できる余地がある限り繰り返す：
   • グリッドから重み付きランダムにセル $c$ を選択。
   • セル $c$ を互いに重ならない三角形またはチョーク（chock）に分解。
   • 面積に基づいて重み付けし、ランダムな領域 $t$ を選択。
   • $t$ から一様サンプリングで点 $p$ を選び追加。
   • $p$ を中心とし半径 $r$ の円をグリッドから切り抜く。

注記：チョークとは、円、放射状の線分、接線によって囲まれた 3 辺を持つ形状を指します。