Abstract
From a single-attribute raster layer in which each cell is assigned a numerical value, a connected set of a specified number of cells that has the maximum (or minimum) total value is selected. This is a highly common decision problem in the context of raster-based geographic information systems (GIS) and seems general enough to deserve inclusion in the standard functionality of such systems. Yet it is a computationally difficult optimization problem, for which no efficient exact solution method has been found. This article presents a new dynamic programming-based heuristic method for the problem. Its performance is tested with randomly generated raster layers with various degrees of spatial autocorrelation. Results suggest that the proposed heuristic is a promising alternative to the existing integer programming-based exact method, as it can handle significantly larger raster data with fair accuracy.
Acknowledgments
The author thanks the anonymous reviewers for their valuable and constructive comments on an earlier draft of the article. Any errors are, of course, the author's responsibility.