The spatial scan statistic  is the most used measure for cluster strenght. The evaluation of all possible subsets of regions in a large dataset is computationally infeasible. Many heuristics have appeared recently to compute approximate values that maximizes the logarithm of the likelihood ratio. The Fast Subset Scan  finds exactly the optimal irregularly spatial cluster; however, the solution may not be connected. The spatial cluster detection problem was formulated as the classic knapsack problem , and modeled as a bi-objective unconstrained combinatorial optimization problem. Dynamic programming relies on the principle that, in an optimal sequence of decisions or choices, each sub-sequence must also be optimal. During the search for a solution it avoids full enumeration by pruning early partial decision solutions that cannot possibly lead to optimal solutions.
We propose a fast, exact algorithm to make detection and inference of arbitrarily shaped connected spatial clusters in aggregated area maps based on constrained dynamic programming.