Menu
Redrawing lines for redistricting plans that represent U.S. congressional districts is a tricky business. There are many laws that dictate how lines can and cannot be drawn, such as contiguity. In fact, building all redistricting plans for a single U.S. state is an intractable problem. Researchers have turned to heuristics in order to analyze current redistricting plans. Many of these heuristics (e.g. local search heuristics and Markov chain Monte Carlo algorithms) used by researchers form new congressional districts by switching the smaller pieces (e.g. precincts or census blocks) that make up congressional districts from one congressional district to another.
In this paper, we discuss the various natural definitions involved in satisfying rules for contiguity and simply connectedness of precincts or census blocks and how these relate to contiguity and simply connectedness of congressional districts. We also propose and analyze several constructions to alleviate violations of contiguity and simply connectedness in precincts and census blocks. Finally, we develop efficient algorithms that allow practitioners to assess redistricting plans using local search heuristics or Markov chain Monte Carlo algorithms efficiently.