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 -