技術要約：先史時代の人類移動における効率的な経路再構築

1. 問題提起

先史時代の移動ルートの再構築は、山脈や急峻な斜面といった地形的制約を考慮した「実効距離」を算出するために、最小コスト経路解析（LCPA）に依存している。標準的なLCPAの実装では、60秒角のETOPOデータセットのような高解像度のデジタル標高モデル（DEM）を使用し、これらは高密度な格子グラフへと離散化される。

主要な課題として特定されたのは、深刻な計算上のボトルネックである。最短経路を見つけるために使用されるダイクストラ法は、$O(|E| + |V| \log |V|)$ の時間計算量を持つ。大陸規模のデータセットに高解像度で適用した場合、頂点数（$|V|$）およびエッジ数（$|E|$）が極めて膨大になり、実用的なメモリ容量や実行時間を超えてしまう。

一様なデータ圧縮（ダウンサンプリング）による従来の回避策は、方法論的に欠陥がある。一様に格子解像度を低下させると、地形を無差別に平滑化してしまい、歴史的に人類の移動を規定してきた重要な微細な地形的特徴（例：狭い山間部や急峻な谷の回廊）を消失させてしまう。これにより、アルゴリズムが本来必要な谷を通るのではなく、人工的に平坦化された山の上を通過するといった、構造的に歪んだ経路再構築が引き起こされる。

2. 手法：適応型ウェーブレット圧縮

解像度とスケールのジレンマを解決するために、著者らは高速ウェーブレット変換（FWT）に基づく適応型マルチスケール・ルーティング・フレームワークを提案している。静的な一様格子ではなく、この手法は地形の複雑性が高い場所にのみ高解像度を動的に割り当て、一方で均質な領域を圧縮する。

コア構成要素：

• マルチスケール分解： 地形標高関数 $f(x, y)$ は、ウェーブレット理論を用いて、粗いベースライン近似と、スケール間の幾何学的差異を表す詳細係数（$d_{\ell,k}$）へと分解される。
• Best-N-Term しきい値処理： 圧縮戦略として、上位 $N$ 個の大きなウェーブレット詳細係数のみを保持する手法が適用される。しきい値以下の係数（平坦で均質な領域を表す）は破棄され、それらの領域は大きなマクロブロックへと統合される。
• 基底関数の選択： 本論文は、区分定数関数（$N_1$ / ハール・ウェーブレット）ではなく、**連続区分線形関数（$N_2$ B-スプライン / ハット・ウェーブレット）**を利用することで、先行研究を拡張している。
  • $N_1$ は、スケールの境界において不連続なブロック状の表現（人工的な「崖」）を生み出す。
  • $N_2$ は、重なり合うテント型のサポートを作成し、パスファインディング・アルゴリズムに適した、より滑らかで連続的な地形表現を実現する。
• 階層的検証： （大きな「平坦な」ブロックの中に隠れた微細な障壁（例：狭い峡谷）を誤って消去することを防ぐため、ある領域が統合されるためには、そのすべての構成サブ領域に有意な地形的詳細が含まれていないことを保証する、ボトムアップ型の検証スキームが導入されている。

適応型ダイクストラ・アルゴリズム

ルーティング・アルゴリズムは、この不規則なマルチスケール・メッシュをナビゲートするように構造的に適応されている：

1. 動的グラフ構築： 頂点は、$1.5 \times 1.5$ km のセルから数十キロメートルに及ぶブロックまで、空間的な広がりを表す。
2. スケールを考慮したエッジ定義：
   • 接続性は、基底関数のサポートの交差によって定義される。$N_2$ ウェーブレットの場合、エッジはサポートが重なる場合（$\text{supp}(\psi) \cap \text{supp}(\psi) \neq \emptyset$）に存在する。
   • エッジの重みは、接続された頂点の特定の解像度レベル間の物理的距離（ハバーサイン公式）と傾斜に基づいて動的に計算される。
3. スケール依存のペナルティ： アルゴリズムが数学的に平滑化されたブロックを人工的なショートカットとして利用してしまうのを防ぐため、粗い（圧縮された）レベルを横断するエッジに対してペナルティ係数 $\alpha_\ell \geq 1.0$ が適用される。これにより、失われたサブスケールの粗さを補うために大きなブロックの通過コストを増大させ、トポロジーの忠実度を確保する。

3. 主な貢献

• 新規の応用： これは、考古学的な移動モデリングに特化した適応型ウェーブレット圧縮の初の実装であり、非考古学的なLCPフレームワークを拡張したものである。
• アルゴリズムの適応： ウェーブレット変換によって生成された動的なマルチスケール・メッシュを横断するための、ダイクストラ・アルゴリズムの数学的な適応（特に区分線形基底における接続規則を含む）を詳述している。
• 基底の比較： 区分定数（$N_1$）と区分線形（$N_2$）の基底に関する比較分析を提供し、$N_2$ が中程度の圧縮率において優れたトポロジーの忠実度を示す一方で、$N_1$ は極端な圧縮において堅牢であることを示している。
• 実装： 本手法は ArcheoGra.jl Julia パッケージ内に実装されており、大規模な空間モデリングのための実用的なツールを提供している。

4. 結果およびケーススタディ

本フレームワークは、ETOPO データセットを用い、標準的な一様ダイクストラ・アルゴリズムと比較して、2つのシナリオでベンチマークテストが行われた。

A. マクロリージョナル・ルーティング（イベリア半島から西アルプスまで）

• パフォーマンス： 適応型フレームワークは、98.81% の圧縮率（データの約1.2%のみを保持）を達成しながら、ダイクストラ法によって処理される頂点数を80%以上削減した（約285,000 から 約52,000 へ）。
• 忠実度： 98% 以上の詳細係数を破棄したにもかかわらず、グローバルなルーティング・トポロジーは保持された。アルゴリズムは圧縮された平原を正常に通過する一方で、ピレネー山脈やアルプスに遭遇すると動的に高解像度へと戻り、非圧縮の参照モデルと同じ主要な回廊を特定した。
• 基底の比較： 高圧縮時（$N=50,000$）において、$N_2$ 基底は総コスト誤差を $N_1$ の18.6%に対し、10.7%に低減させた。

B. 微細地形の課題（東アルプス）

• 谷の保存問題： 密集した険しい地形において、極端な圧縮（$N=5,000$）は「障壁の塗りつぶし（barrier smearing）」を引き起こし、アルゴリズムが急峻な峰や深い谷を平滑化してしまい、山を横切る非現実的な直線経路を生じさせた。
• 中程度の圧縮： $N=150,000$ では、アルゴリズムは山を障壁として認識したが、狭い峠を保持できず、大幅な迂回を強いる結果となった。
• 要求される解像度： 狭い谷の回廊を正確に再構築するには、より高い詳細レベル（圧縮率 約32%）が必要であることを示しており、これは適応型メッシュが複雑性を軽減する一方で、険しい地形におけるサブスケールのトポロジー的接続性を維持するには、十分なデータ解像度が依然として必要であることを示している。

5. 意義と主張

本論文は、この適応型マルチスケール・フレームワークが、考古学的な空間モデリングにおける解像度とスケールのジレンマを効果的に解決すると主張している。

• 計算の実現可能性： これにより、標準的な計算限界を超えることなく、高解像度データ（60秒角）を用いた大陸規模の全対最短経路（APSP）の計算が可能になる。
• トポロジーの完全性： 一様なダウンサンプリングとは異なり、ウェーブレット・アプローチは局所的な分散が高い場所に正確に高解像度を保持することで、重要な地形的特徴（チョークポイント、峠）を保存する。
• 実用的有用性： 本手法は、研究者が計算効率とトポロジーの忠実度のバランスを取るための柔軟なメカニズムを提供する。保持する係数の数を調整することで、マクロリージョナル・モデルでは積極的な圧縮（>95%）を行いながら、ミクロリージョナル・モデルでは狭い谷を保存する能力を維持することができる。

著者らは、この数学的に最適化されたツールが、特にHESCORプロジェクトの文脈において、将来の先史時代の人類移動や原材料交換の研究に向けた、極めて正確で大規模な最短経路行列の生成を計算可能にすると結論づけている。