The dynamic programming algorithm is thus modified to consider (i) a geographical proximity constraint and (ii) a connectivity constraint, for each region j. Assuming that the geographical proximity of a region j contains k regions, the geographical dynamic scan guarantees the optimal solution within the collection of 2ˆk subsets, searching for only a small number of subsets, which depends almost linearly on k, on average.