An efficient multiple scanning order algorithm for accumulative least-cost surface calculation

Abstract

The least-cost surface (LCS) calculation is a compute-intensive problem conventionally solved by the queue-based Dijkstra’s algorithm. Alternative raster-based scanning algorithms have also been proposed which use a moving window to scan the whole study area iteratively. Here we propose improvements to the raster-based algorithms. The main improvement is to implement multiple scanning orders (MSO) to replace the conventional single scanning order (SSO, typically from upper-left corner to lower-right corner, row by row). We compared the performance of different algorithms over different cost surfaces and with different numbers of source points. The comparison shows that a raster-based algorithm adopting MSO has a substantially better performance than a conventional raster-based algorithm using SSO. An MSO raster-based algorithm is generally comparable to the queue-based Dijkstra’s algorithm, and surpasses the latter over a relatively simple cost surface (e.g. in which the cost is resampled) and/or when the number of source points is relatively large. Our empirical experiments suggest that MSO reduces the time complexity from to $\mathrm{\Theta }(N^2)$ to $\mathrm{\Theta }(\mathrm{NlogN}).$ Additionally, we found that the MSO raster-based algorithm can be easily parallelized using shared-memory parallel programming.

Keywords:

• Least-cost surface
• geocomputation
• spatial analysis

Acknowledgement

We sincerely thank the valuable contributions given by the editor (Professor Shawn Laffan) and the anonymous reviewers.

Data and codes availability statement

The relevant datasets of this study are archived in the zenodo site (https://zenodo.org/record/6339694#.Yif6u3rMKUl).

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Yuanzhi Yao

Yuanzhi Yao is a postdoctoral research fellow at the College of Forestry and Wildlife Sciences, Auburn University and a research professor at the School of Geographic Sciences, East China Normal University. He develops hydrological, and water quality components of terrestrial ecosystem model and disseminates research results on climatic and anthropogenic influences on the physical and biogeochemical processes within the inland water ecosystem and the associate greenhouse gas emissions.

Xun Shi

Xun Shi is a professor at the Department of Geography, Dartmouth College. His specialty is in geographic information systems (GIS), quantitative spatial analysis and modeling, and the geocomputational approach. He has explored the applications of GI technologies in various domains, particularly in health studies, digital soil mapping, urban and regional planning, public participation, and renewable energy studies.

Zekun Wang

Zekun Wang received his Ph.D degree (2022) at the Department of Mechanical Engineering, Auburn University. He mainly engaged in the application of machine learning methods in image processing. He also concerns about the energy usage and reliability of electrical device, and whisker growing behavior and suppression under extreme environment.