Efficient regionalization techniques for socio‐economic geographical units using minimum spanning trees

Abstract

Abstract Regionalization is a classification procedure applied to spatial objects with an areal representation, which groups them into homogeneous contiguous regions. This paper presents an efficient method for regionalization. The first step creates a connectivity graph that captures the neighbourhood relationship between the spatial objects. The cost of each edge in the graph is inversely proportional to the similarity between the regions it joins. We summarize the neighbourhood structure by a minimum spanning tree (MST), which is a connected tree with no circuits. We partition the MST by successive removal of edges that link dissimilar regions. The result is the division of the spatial objects into connected regions that have maximum internal homogeneity. Since the MST partitioning problem is NP‐hard, we propose a heuristic to speed up the tree partitioning significantly. Our results show that our proposed method combines performance and quality, and it is a good alternative to other regionalization methods found in the literature. Keywords: RegionalizationConstrained clusteringGraph partitioningOptimizationZone designCensus data analysis Acknowledgements Renato Assunção's research is partially supported by CNPq (grant 305567/2004‐7). Marcos Neves' research has been supported by EMBRAPA. Gilberto Camara's work is partially funded by CNPq (grants PQ‐300557/19996‐5 and 550250/2005‐0) and FAPESP (grant 04/11012‐0). Corina Freitas' research has been partially supported by CNPq (grant 305546/2003‐1).

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 437 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.