Formation of a near Optimal Solution for Raster Region having Max/Min Cell Value

Abstract

Raster region selection problem for finding a Max/Min Region with connected constraint is a unique problem in the field of Geographical Information Systems (GIS), for which an efficient solution is not yet designed. Such kind of a region selection problem can be very useful in different decision making problems. For finding a region of such interest, there are at most 4*3(k-2) number of unique regions when using 4-Adjacency region rule as connected constraint, 'k' here, is the user specified number of cells to be included in the region. So for finding a 50-cell Max/Min raster region, there can be more than 32,000,000 unique regions. The problem is computationally complex in finding out a Max/Min region for larger input raster, so only approximate solution could be designed. The best known heuristic till date takes 29 hours to find out an optimal region for a 180* 180 raster input grid. Focus of this research is to develop an efficient solution for the same problem which can work with bigger data and form out a near optimal region in a few minutes. The heuristic developed in the research uses in-memory greedy algorithm approach which has proved superior when compared with other approaches in terms of accuracy, efficiency and space utilized by the heuristic, and it was tested against real-life data. The results suggest that with higher degree of spatial autocorrelation in the data, this heuristic is very useful and has the tendency to be used in different decision making problems.