TY - JOUR
T1 - Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
AU - King, Douglas M.
AU - Jacobson, Sheldon H.
AU - Sewell, Edward C.
PY - 2014
Y1 - 2014
N2 - Graph partitioning is an intractable problem that arises in many practical applications. Heuristics such as local search generate good (though suboptimal) solutions in limited time. Such heuristics must be able to explore the solution space quickly and, when the solution space is constrained, differentiate feasible solutions from infeasible ones. Geographic zoning problems allocate some resource (e.g., political representation, school enrollment, police patrols) to contiguous zones modeled by partitions of an embedded planar graph. Each vertex corresponds to an area of the plane (e.g., census block, town, county), and local search moves one area from its current zone to a different zone in each iteration. Enforcing contiguity constraints may require significant computation when the graph is large. While existing algorithms require linear or polylogarithmic time (in the number of vertices) to assess contiguity in each local search iteration, the geo-graph paradigm shows how contiguity can be verified by examining only the set of vertices that border the transferred area (i.e., those areas whose boundaries share at least a single point with the boundary of the transferred area). This paper develops efficient algorithms that examine these vertices more quickly than traditional search-based methods, allowing practitioners to more fully consider their zoning options when creating zones with local search.
AB - Graph partitioning is an intractable problem that arises in many practical applications. Heuristics such as local search generate good (though suboptimal) solutions in limited time. Such heuristics must be able to explore the solution space quickly and, when the solution space is constrained, differentiate feasible solutions from infeasible ones. Geographic zoning problems allocate some resource (e.g., political representation, school enrollment, police patrols) to contiguous zones modeled by partitions of an embedded planar graph. Each vertex corresponds to an area of the plane (e.g., census block, town, county), and local search moves one area from its current zone to a different zone in each iteration. Enforcing contiguity constraints may require significant computation when the graph is large. While existing algorithms require linear or polylogarithmic time (in the number of vertices) to assess contiguity in each local search iteration, the geo-graph paradigm shows how contiguity can be verified by examining only the set of vertices that border the transferred area (i.e., those areas whose boundaries share at least a single point with the boundary of the transferred area). This paper develops efficient algorithms that examine these vertices more quickly than traditional search-based methods, allowing practitioners to more fully consider their zoning options when creating zones with local search.
KW - Graph contiguity
KW - Graph partitioning
KW - Planar graphs
KW - Political districting
UR - http://www.scopus.com/inward/record.url?scp=84921700531&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84921700531&partnerID=8YFLogxK
U2 - 10.1007/s10107-014-0762-4
DO - 10.1007/s10107-014-0762-4
M3 - Article
AN - SCOPUS:84921700531
SN - 0025-5610
VL - 149
SP - 425
EP - 457
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -