Uniform and balanced sampling of connected planar graph partitions is hard unless RP=NP, the flip walk mixes exponentially slowly on explicit triangulation families, and tractable cases include series-parallel and bounded-treewidth graphs.
The Gerrymandering Jumble: Map Projections Permute Districts' Compactness Scores
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
In political redistricting, the compactness of a district is used as a quantitative proxy for its fairness. Several well-established, yet competing, notions of geographic compactness are commonly used to evaluate the shapes of regions, including the Polsby-Popper score, the convex hull score, and the Reock score, and these scores are used to compare two or more districts or plans. In this paper, we prove mathematically that any map projection from the sphere to the plane reverses the ordering of the scores of some pair of regions for all three of these scores. Empirically, we demonstrate that the effect of using the Cartesian latitude-longitude projection on the order of Reock scores is quite dramatic.
fields
cs.CC 1years
2019 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Complexity and Geometry of Sampling Connected Graph Partitions
Uniform and balanced sampling of connected planar graph partitions is hard unless RP=NP, the flip walk mixes exponentially slowly on explicit triangulation families, and tractable cases include series-parallel and bounded-treewidth graphs.