Redistricting, a primer.
An excellent review of the redistricting process in the United States is A Citizen's Guide to Redistricting by Justin Levitt. [Levitt] In the United States a census is taken every 10 years. As population grows in one region and shrinks in another, states gain or lose seats in the House of Representatives. Additionally, as populations shift within states, some congressional districts have populations that are too large, others too small. As a result of these demographic shifts, states typically must redraw their congressional districts every decade. This process is called redistricting and must be completed before the first federal election following the release of the census data.
Redistricting Process: State governments are responsible for redrawing their congressional districts in response to changing census data. An ideal redistricting plan will generate districts of equal population that are contiguous and "compact". (We note here that the term compact does not refer to the mathematical concept of compactness, but rather to a qualitative notion of enclosing an area with a minimum of perimeter.) These three qualities are the most important. Secondary qualities include respect for city and county borders and respect for significant geographic features like rivers or mountain ranges. Tertiary qualities include having populations of similar interests, appropriate minority status, similar political affiliations.
The Constitution of the United States gives state legislatures the power to determine how each state's congressional representatives are chosen (Article 1, Section 4). Logically, this includes the power to draw the congressional districts that are each allocated a seat in the House of Representatives. Each state's legislature develops one or more preliminary redistricting plans, typically in a pre-existing legislative committee, or in a special committee formed for the sole purpose of redistricting. In some states, these special committees consist of citizens with no official ties to the state government, but most are made up of state representatives. [FairVote]
There is a large degree of variability in the methods used by these committees in the redistricting process. If a state has not experienced a large degree of demographic shift since the last census, for instance, its redistricting committee would probably use the state's current districts as a starting point for drawing the new ones. In states with shifting political leadership, a new majority party could also wish to drastically change the plan, in which case the legislative committee (presumably made up of majority party's members) might start with a more political map. [Levitt] Though these details vary greatly from state to state, almost all committees use some sort of software suite (Esri's ArcGIS or Caliper's Maptitude, for instance) to draw their plans. These plans are then subject to a vote by the whole of the state legislature, and often must also pass through the governor's office before they become official.
District Qualities: Our goal here is to present some of the technical issues associated with the task of redistricting. It should be noted that the process of redistricting is never likely to be wholly automated. That said, the people and committees in charge of developing redistricting plans still rely heavily on large data sets and computation to draw districts. We hope that by reading this paper and playing with our applet the reader will get an idea of what is involved and perhaps even contribute to the development of new tools to inform this process.
The quality of equal population has emerged over years of legal opinion to be the most important feature of any redistricting plan. Though it may seem obvious that all districts should have equal population to satisfy the "one person, one vote" philosophy, districts with large non-voting populations (e.g. children, non-citizens, people in prison) confer proportionally more weight to voters in those districts. [Bullock] There does not appear to be any inclination on the part of the courts to address this issue. Hence, we use the census data directly without having to remove ineligible voters.
The quality of compactness of districts is less well-defined. There have been several measures of compactness used by the courts over the years. Generally, the area of a district should be enclosed by a boundary of minimum perimeter. For a given perimeter the circle encloses the most area. This follows from the famous isoperimetric inequality. [Oprea] Clearly, we cannot have circular congressional districts, but minimizing perimeter seems to be a desirable characteristic. However, courts have been willing to sacrifice compactness for the sake of other qualities—particularly in states under federal supervision via the Voting Rights Act. (reference) Consider, for example, the 12th district in North Carolina shown in this figure.
The 12th congressional district (yellow) of North Carolina in 2010. (arcGIS)
If a circle is considered the ideal compact shape, this district is far from compact. This figure shows a similarly non-compact district.
The 3rd congressional district (yellow) of Maryland in 2010. (arcGIS)
This figure shows the districts in Iowa.
The congressional districts in Iowa in 2010. (from http://nationalatlas.gov)
Unlike the previous examples, these districts are relatively compact. Note also that this map respects county lines.
The work here focuses on the primary attributes of equal population, contiguity, and compactness. Given a population density function, \(\rho\), on a state, we present a few different ways of generating districts of equal population, that are compact and contiguous. We also include an applet that allows the user to draw their own district maps using a sweep circle algorithm.