Technical Summary: Efficient Path Reconstruction in Prehistoric Human Migration

1. Problem Statement

Reconstructing prehistoric migration routes relies on Least-Cost Path Analysis (LCPA) to calculate "effective distances" that account for topographic constraints like mountain ranges and steep slopes. Standard LCPA implementations utilize high-resolution Digital Elevation Models (DEMs), such as the 60 arc-second ETOPO dataset, which are discretized into dense grid graphs.

The primary challenge identified is a severe computational bottleneck. Dijkstra's algorithm, used to find shortest paths, has a time complexity of $O(|E| + |V| \log |V|)$. When applied to continental-scale datasets at high resolutions, the number of vertices ($|V|$) and edges ($|E|$) becomes prohibitively large, exceeding practical memory and runtime capacities.

Conventional workarounds, such as uniform data compression (downsampling), are methodologically flawed. Uniformly reducing grid resolution indiscriminately smooths the landscape, erasing critical fine-scale topographic features (e.g., narrow mountain passes, steep valley corridors) that historically dictated human movement. This leads to structurally distorted path reconstructions where algorithms may route paths over artificially flattened mountains rather than through necessary valleys.

2. Methodology: Adaptive Wavelet Compression

To resolve the resolution-scale dilemma, the authors propose an adaptive multi-scale routing framework based on the Fast Wavelet Transform (FWT). Instead of a static uniform grid, the method dynamically allocates high resolution only where topographic complexity is high, while compressing homogeneous regions.

Core Components:

• Multi-Scale Decomposition: The topographic elevation function $f(x, y)$ is decomposed using wavelet theory into a coarse baseline approximation and detail coefficients ($d_{\ell,k}$) representing geometric differences between scales.
• Best-N-Term Thresholding: A compression strategy is applied where only the $N$ largest wavelet detail coefficients are retained. Coefficients below a threshold (representing flat, homogeneous areas) are discarded, merging those regions into large macroscopic blocks.
• Basis Function Selection: The paper extends previous work by utilizing continuous piecewise-linear functions ($N_2$ B-Splines / Hat wavelets) rather than piecewise-constant functions ($N_1$ / Haar wavelets).
  • $N_1$ creates disjoint, blocky representations with artificial "cliffs" at scale boundaries.
  • $N_2$ creates overlapping, tent-shaped supports, resulting in a smoother, continuous terrain representation that better suits pathfinding algorithms.
• Hierarchical Validation: To prevent the accidental erasure of sub-scale barriers (e.g., a narrow gorge hidden within a larger "flat" block), a bottom-up validation scheme ensures a region is only consolidated if all constituent sub-regions lack significant topographic detail.

The Adaptive Dijkstra Algorithm

The routing algorithm is structurally adapted to navigate this irregular, multi-scale mesh:

1. Dynamic Graph Construction: Vertices represent spatial extents ranging from $1.5 \times 1.5$ km cells to blocks spanning tens of kilometers.
2. Scale-Aware Edge Definition:
   • Connectivity is defined by the intersection of basis function supports. For $N_2$ wavelets, an edge exists if supports overlap ($\text{supp}(\psi) \cap \text{supp}(\psi) \neq \emptyset$).
   • Edge weights are calculated dynamically based on the physical distance (Haversine formula) and the slope between the specific resolution levels of connected vertices.
3. Scale-Dependent Penalties: To prevent the algorithm from exploiting mathematically smoothed blocks as artificial shortcuts, a penalty factor $\alpha_\ell \geq 1.0$ is applied to edges crossing coarser (compressed) levels. This inflates the cost of traversing large blocks to compensate for lost sub-scale roughness, ensuring topological fidelity.

3. Key Contributions

• Novel Application: This is the first application of adaptive wavelet compression specifically for archaeological migration modeling, extending previous non-archaeological LCP frameworks.
• Algorithmic Adaptation: The paper details the mathematical adaptation of Dijkstra's algorithm to traverse a dynamic, multi-scale mesh generated by wavelet transforms, including specific connectivity rules for piecewise-linear bases.
• Basis Comparison: The study provides a comparative analysis of piecewise-constant ($N_1$) versus piecewise-linear ($N_2$) bases, demonstrating that $N_2$ offers superior topological fidelity at moderate compression rates, while $N_1$ remains robust at extreme compression.
• Implementation: The method is implemented within the ArcheoGra.jl Julia package, providing a practical tool for large-scale spatial modeling.

4. Results and Case Studies

The framework was benchmarked against standard uniform Dijkstra algorithms using the ETOPO dataset across two scenarios:

A. Macro-Regional Routing (Iberian Peninsula to Western Alps)

• Performance: The adaptive framework achieved a compression rate of 98.81% (retaining only ~1.2% of data) while reducing the vertex count processed by Dijkstra's algorithm by over 80% (from ~285,000 to ~52,000).
• Fidelity: Despite discarding >98% of detail coefficients, the global routing topology was preserved. The algorithm successfully navigated compressed plains but dynamically reverted to high resolution when encountering the Pyrenees and Alps, identifying the same major corridors as the uncompressed reference.
• Basis Comparison: At high compression ($N=50,000$), the $N_2$ basis reduced total cost error to 10.7% compared to 18.6% for $N_1$.

B. Micro-Topographic Challenges (Eastern Alps)

• Valley Preservation Problem: In dense, rugged terrain, extreme compression ($N=5,000$) caused "barrier smearing," where the algorithm smoothed out steep peaks and deep valleys, resulting in unrealistic straight-line paths across mountains.
• Moderate Compression: At $N=150,000$, the algorithm recognized mountains as barriers but failed to preserve narrow passes, forcing massive detours.
• Resolution Requirement: Accurate reconstruction of narrow valley corridors required a higher detail level (compression rate ~32%), demonstrating that while adaptive meshes reduce complexity, preserving sub-scale topological connectivity in rugged terrain still necessitates sufficient data resolution.

5. Significance and Claims

The paper claims that this adaptive multi-scale framework effectively resolves the resolution-scale dilemma in archaeological spatial modeling.

• Computational Feasibility: It enables the calculation of All-Pairs Shortest Paths (APSP) across continental domains using high-resolution data (60 arc-second) without exceeding standard computational limits.
• Topological Integrity: Unlike uniform downsampling, the wavelet approach preserves critical topological features (choke points, passes) by retaining high resolution exactly where local variance is high.
• Practical Utility: The method provides a flexible mechanism for researchers to balance computational efficiency against topological fidelity. It allows for aggressive compression (>95%) in macro-regional models while maintaining the ability to conserve narrow valleys in micro-regional models by adjusting the retained coefficient count.

The authors conclude that this mathematically optimized tool makes the generation of highly accurate, massive shortest-path matrices computationally feasible for future research into prehistoric migration and raw material exchange, specifically within the context of the HESCOR project.