De-coupled NeuroGF for Shortest Path Distance Approximations on Large Terrain Graphs

The ability to acquire high-resolution, large-scale geospatial data at an unprecedented using LiDAR and other related technologies has intensified the need for scalable algorithms for terrain analysis, including shortest-path-distance (SPD) queries on large-scale terrain digital elevation models (DEMs). In this paper, we present a neural data structure for efficiently answering SPD queries approximately on a large terrain DEM, which is based on the recently proposed neural geodesic field (NeuroGF) framework (Zhang et al., 2023)---the state-of-the-art neural data structure for estimating geodesic distance.In particular, we propose a decoupled-NeuroGF data structure combined with an efficient two-stage mixed-training strategy, which significantly reduces computational bottlenecks and enables efficient training on terrain DEMs at a scale not feasible before. We demonstrate the efficacy of our approach by performing detailed experiments on both synthetic and real data sets.For instance, we can train a small model with around 70000 parameters on a terrain DEM with 16 million nodes in a matter of hours that can answer SPD queries with 1\% relative error in at most 10ms per query.

Modern mapping technologies such as LiDAR have made detailed 3D terrain models widely available. However, it is still extremely time-consuming to query the shortest path between two points between in the terrain, an essential operation in many geospatial applications (e.g. flood risk analysis, disaster modeling). We built neural network-based systems which can quickly answer shortest path queries between any two points in a large-scale and detailed terrains by splitting the neural network training into two parts. The first part helps the neural network learn a coarse representation of the terrain and the second part trains a final lightweight module to compute the shortest path approximation. Our two-stage neural approach helps enable geospatial analysis tasks for terrains of unprecedented size.