Name
Abstract | ||
|---|---|---|
Redistricting is the process of dividing a geographic area consisting of spatial units—often represented as spatial polygons—into smaller districts that satisfy some properties. It can therefore be formulated as a set partitioning problem where the objective is to cluster the set of spatial polygons into groups such that a value function is maximized [1]. Widely used algorithms developed for point-based data sets are not readily applicable because polygons introduce the concepts of spatial contiguity and other topological properties that cannot be captured by representing polygons as points. Furthermore, when clustering polygons, constraints such as spatial contiguity and unit distributedness should be strategically addressed. Toward this, we have developed the Constrained Polygonal Spatial Clustering (CPSC) algorithm based on the {\rm A}^\ast search algorithm that integrates cluster-level and instance-level constraints as heuristic functions. Using these heuristics, CPSC identifies the initial seeds, determines the best cluster to grow, and selects the best polygon to be added to the best cluster. We have devised two extensions of CPSC—CPSC* and CPSC*-PS—for problems where constraints can be soft or relaxed. Finally, we compare our algorithm with graph partitioning, simulated annealing, and genetic algorithm-based approaches in two applications—congressional redistricting and school districting. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/TKDE.2011.140 | Knowledge and Data Engineering, IEEE Transactions |
Keywords | Field | DocType |
computational geometry,geographic information systems,pattern clustering,search problems,set theory,A* search algorithm,CPSC*-PS,CPSC-CPSC*,cluster-level constraints,congressional redistricting,constrained polygonal spatial clustering algorithm,geographic area division,heuristic functions,instance-level constraints,point-based data sets,redistricting process,relaxed constraints,school districting,set partitioning problem,soft constraints,spatial contiguity constraints,spatial polygons,topological properties,unit distributedness constraints,value function maximization,Spatial clustering,constraint-based processing,data mining,polygonal clustering,spatial databases and GIS | Data mining,Search algorithm,Computer science,Computational geometry,Artificial intelligence,Cluster analysis,Graph partition,Simulated annealing,Contiguity,Polygon,Mathematical optimization,Constrained clustering,Machine learning | Journal |
Volume | Issue | ISSN |
24 | 11 | 1041-4347 |
Citations | PageRank | References |
2 | 0.39 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Deepti Joshi | 1 | 62 | 5.55 |
| Leen-kiat Soh | 2 | 592 | 81.43 |
| A Samal | 3 | 1033 | 213.54 |