Spatial Cluster Detection Through a Dynamic Programming Approach

This chapter reviews a dynamic programming scan approach to the detection and inference of arbitrarily shaped spatial clusters in aggregated geographical area maps, which is formulated here as a classic knapsack problem. A polynomial algorithm based on constrained dynamic programming is proposed, the spatial clusters detection dynamic scan. It minimizes a bi-objective vector function, finding a collection of Pareto optimal solutions. The dynamic programming algorithm is adapted to consider geographical proximity between areas, thus allowing a disconnected subset of aggregated areas to be included in the efficient solutions set. It is shown that the collection of efficient solutions generated by this approach contains all the solutions maximizing the spatial scan statistic. The plurality of the efficient solutions set is potentially useful to analyze variations of the most likely cluster and to investigate covariates.