A simulated annealing strategy for the detection of arbitrarily shaped spatial clusters

We propose a new graph-based strategy for the detection of spatial clusters of arbitrary geometric form in a map of geo-referenced populations and cases. Our test statistic is based on the likelihood ratio test previously formulated by Kulldorff and Nagarwalla for circular clusters. A new technique of adaptive simulated annealing is developed, focused on the problem of finding the local maxima of a certain likelihood function over the space of the connected subgraphs of the graph associated to the regions of interest. Given a map with n regions, on average this algorithm finds a quasi-optimal solution after analyzing sn log(n) subgraphs, where s depends on the cases density uniformity in the map. The algorithm is applied to a study of homicide clusters detection in a Brazilian large metropolitan area. (C) 2002 Elsevier B.V. All rights reserved.