Change search
ReferencesLink to record
Permanent link

Direct link
A method for finding a least-cost wide path in raster space
KTH, School of Architecture and the Built Environment (ABE), Urban Planning and Environment, Geoinformatics.ORCID iD: 0000-0001-5572-7395
2016 (English)In: International Journal of Geographical Information Science, ISSN 1365-8816, E-ISSN 1365-8824, Vol. 30, no 8, 1469-1485 p.Article in journal (Refereed) PublishedText
Abstract [en]

Given a grid of cells each having an associated cost value, a raster version of the least-cost path problem seeks a sequence of cells connecting two specified cells such that its total accumulated cost is minimized. Identifying least-cost paths is one of the most basic functions of raster-based geographic information systems. Existing algorithms are useful if the path width is assumed to be zero or negligible compared to the cell size. This assumption, however, may not be valid in many real-world applications ranging from wildlife corridor planning to highway alignment. This paper presents a method to solve a raster-based least-cost path problem whose solution is a path having a specified width in terms of Euclidean distance (rather than by number of cells). Assuming that all cell values are positive, it does so by transforming the given grid into a graph such that each node represents a neighborhood of a certain form determined by the specified path width, and each arc represents a possible transition from one neighborhood to another. An existing shortest path algorithm is then applied to the graph. This method is highly efficient, as the number of nodes in the transformed graph is not more than the number of cells in the given grid and decreases with the specified path width. However, a shortcoming of this method is the possibility of generating a self-intersecting path which occurs only when the given grid has an extremely skewed distribution of cost values.

Place, publisher, year, edition, pages
2016. Vol. 30, no 8, 1469-1485 p.
Keyword [en]
Least-cost path, wide path, site selection, raster data modeling
National Category
Discrete Mathematics
URN: urn:nbn:se:kth:diva-187858DOI: 10.1080/13658816.2015.1124435ISI: 000374902300001ScopusID: 2-s2.0-84950111608OAI: diva2:931742

QC 20160530

Available from: 2016-05-30 Created: 2016-05-30 Last updated: 2016-05-30Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Shirabe, Takeshi
By organisation
In the same journal
International Journal of Geographical Information Science
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 8 hits
ReferencesLink to record
Permanent link

Direct link