Redistricting using heuristic-based polygonal clustering

Deepti Joshi, Leen Kiat Soh, Ashok Samal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations


Redistricting is the process of dividing a geographic area into districts or zones. This process has been considered in the past as a problem that is computationally too complex for an automated system to be developed that can produce unbiased plans. In this paper we present a novel method for redistricting a geographic area using a heuristic-based approach for polygonal spatial clustering. While clustering geospatial polygons several complex issues need to be addressed - such as: removing order dependency, clustering all polygons assuming no outliers, and strategically utilizing domain knowledge to guide the clustering process. In order to address these special needs, we have developed the Constrained Polygonal Spatial Clustering (CPSC) algorithm that holistically integrates domain knowledge in the form of cluster-level and instance-level constraints and uses heuristic functions to grow clusters. In order to illustrate the usefulness of our algorithm we have applied it to the problem of formation of unbiased congressional districts. Furthermore, we compare and contrast our algorithm with two other approaches proposed in the literature for redistricting, namely - graph partitioning and simulated annealing.

Original languageEnglish (US)
Title of host publicationICDM 2009 - The 9th IEEE International Conference on Data Mining
Number of pages6
StatePublished - 2009
Event9th IEEE International Conference on Data Mining, ICDM 2009 - Miami, FL, United States
Duration: Dec 6 2009Dec 9 2009

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786


Conference9th IEEE International Conference on Data Mining, ICDM 2009
Country/TerritoryUnited States
CityMiami, FL


  • District formation
  • Polygon
  • Polygonal clustering
  • Redistricitng
  • Spatial data mining

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'Redistricting using heuristic-based polygonal clustering'. Together they form a unique fingerprint.

Cite this