Unbiased Congressional DistrictsAlex [email protected] [email protected] paper presents a strategy for dividinga state into congressional districts using amodified version of Smith and Ryan’s re-cursive shortest splitline algorithm (2007).Our strategy reduces the cost of the com-putation by approximating the populationof a ZIP Code Tabulation Area (ZCTA) asa point mass at its population centroid. Ifthere are N ZCTAs in the state with E to-tal edges, and k districts to be created, ouralgorithm runs in expected O((N2+ E) ·logk) time.1 IntroductionThe determination of congressional district bound-aries within a state is often a controversial pro-cess. Typically, any solution that gives contiguous,equipopulous districts is legal. Therefore, the ma-jority party in the state legislature has wide latitudeto draw districts that bolster its chances in congres-sional elections. Such gerrymandered districts willtypically disperse regions of strong support for theopposition party among the districts so that the ma-jority will control most or all seats.We adopt the following definitions. An unbiaseddistricting is a division of a region into equipopu-lous districts that is developed without any informa-tion about the residents’ voting preferences. A ger-rymandered districting is a division of a region intoequipopulous districts such that the region’s major-ity party is the majority party in every district.2 Related WorkThe literature contains several proposals for gener-ating or maintaining unbiased districts that optimizesome geometric criterion.Given an initial districting, Helbig et. al. heuris-tically maximize district compactness using an iter-ative linear programming technique (1972). In theirmethod, the region is discretized into m existing po-litical zones, such as counties or census tracts, thatare small compared to the whole state and approxi-mately equipopulous. They then proceed as summa-rized in Algorithm 1. Constraint A is the one-voteconstraint: each zone belongs to exactly one district.Constraint B is the equipopulation constraint. It re-lies on the assumption that zones are equipopulous,but this restriction could easily be lifted by rewrit-ing the constraint as an inequality on the popula-tion sum, with some deviation tolerance. The valuefunction to be minimized is simply the summedpopulation-weighted distance of zones from the cen-troids of their districts. Since finding a minimum bybrute force takes O(2m) time, the transportation al-gorithm is used; the details are out of the scope ofthis paper. Note that this method does not guaranteethat districts will be contiguous.Macmillan presents an innovative solution to thecontiguity problem (Macmillan, 2001). Macmillanfirst presents the connectivity method of checkingcontiguity of a region, which is a streamlined, butstill O(m3), version of connectivity matrix multipli-cation. Macmillan improves on this algorithm byinitially assuming that the regions in the districtingare already connected, and what is being examinedis the decision to either add a single zone to or re-move a single zone from the current region. Sincethe only way the region can become disconnectedis if adding or removing the zone breaks contiguity,we need only examine the single zone and the zonesit borders. Using Macmillan’s switching point tech-nique, it can be determined quickly whether the op-eration breaks contiguity. An initial districting canthen be updated in response to population movementAlgorithm 1 Helbig et. al. linear transportLet ǫ be an arbitrary stagnation threshold.Let m be the total number of zones.Let n be the number of districts.g = m/nLet (ui, vi) be the centroid of zone i.Let pibe the population of zone i.repeatfor All districts j doCompute (aj, bj), the centroid of district j.for All zones i dodij=q(aj− ui)2+ (bj− vi)2if zone i is in district j thenxij= 1elsexij= 0end ifend forend forconstraint A:Xjxij= 1 for all i.constraint B:Xixijpi= g.Using the transportation algorithm, minimizeXiXj(xij· dij· pi) subject to constraintsA,B.for All districts doLet (¯aj,¯bj) be the centroid of the new districtj.end foruntil |¯aj−aj| < ǫ and |¯bj− bj| < ǫ for all j.by simulated annealing. In this process, donor dis-tricts with excess population and recipient districtswith a population deficit are selected at weighted-random by the size of the deviation. A zone totransfer is selected at weighted-random by the sizeof the resulting deviation. So long as the transferwould not break contiguity, it is accepted if it strictlyimproves deviation, and probabilistically acceptedbased on the current annealing temperature other-wise. Macmillan’s algorithm does not optimize forcompactness or any other geometric property, andtherefore may yield results as unattractive as a ger-rymander.The shortest splitline algorithm of Smith andRyan recursively divides the region to be districtedinto two regions (Smith and Ryan, 2007). If the re-gion being divided has an even number of congres-sional seats, the two child regions are equipopulous.If it has an odd number, then one region will be largeenough to have one more seat than the other. Smithand Ryan compute splitlines on a grid sampling ofpopulation. The details of their implementation areonly given as uncommented C source code, and aretherefore not summarized here.Our literature search did not discover any exist-ing work explicitly concerned with optimal gerry-mandering. However, the generalized equitable hamsandwich algorithm of Bespamyatnikh et. al. isapplicable (1999). This algorithm splits a set ofr · p red points and r · q blue points into r regionswith p red points and q blue points using a divide-and-conquer strategy. Using voter registration rolls,registered Democrats (blue points) and Republicans(red points) can be identified with geographic loca-tions. Letting r equal the size of the state’s con-gressional delegation, the majority party will controlevery district in the equitable ham sandwich subdi-vision.3 ImplementationWe have implemented a shortest splitline algorithmusing the basic concepts developed by Smith andRyan (2007), but with the adapted implementationsummarized in Algorithm 2. The algorithm pro-duces districts that are contiguous, and equipopulousto a variable tolerance parameter ǫ. Degeneracy han-dling is not included in the pseudocode, but has beenimplemented and is discussed further in Section 3.3.Smith and Ryan use a raster model for