Search

This paper addresses the problem of computing least-cost-path surfaces for massive grid-based terrains. Our approach follows a modular design, enabling the algorithm to make efficient use of memory, disk, and grid computing environments. We have implemented the algorithm in the context of the GRASS open source GIS system and---using our cluster management tool---in a distributed environment. We report experimental results demonstrating that the algorithm is not only of theoretical and conceptual interest but also performs well in practice. Our implementation outperforms standard solutions as dataset size increases relative to available memory and our distributed solver obtains near-linear speedup when preprocessing large terrains for multiple queries.