Preventing gerrymandering: a moving-knife algorithm to draw congressional districts
提出一种移动刀算法，通过最大化地理紧凑性来无党派地绘制美国众议院选区，防止政党操纵选区边界，且计算可行。
To prevent gerrymandering of U.S. House of Representative districts, we describe and apply a computationally feasible moving-knife algorithm (MKA) to draw congressional districts that are nonpartisan and compact. MKA maximizes a measure of geographic compactness that precludes political parties from influencing the drawing of district boundaries. MKA begins by constructing the “minimum bounding circle” of a state, which encircles it as tightly as possible. The state’s Reock score—the ratio of its physical area to the larger area of its bounding circle, which varies between 0 and 1—is a measure of the compactness of a state as well as districts within a state. A “moving knife” sequentially cuts districts from a state that maximizes each district’s Reock score, providing an objective way of making districts relatively “squarish.” We show that the median Reock score of MKA districts of a state is generally equal to or greater than that of its actual districts, and sometimes substantially so. We also show that MKA districts are, on average, as competitive as the actual districts. MKA precludes the majority party from manipulating district boundaries (e.g., by pack-and-crack) to gain an advantage, thereby thwarting gerrymandering.