Political districting is an important and mathematically challenging problem. In fall 2023, the Simons Laufer Mathematical Sciences Institute (SLMath) hosted a semester program on algorithms, fairness, and equity, focusing on the intersection of computational tools and the many notions of fairness that arise in different mathematical and societal contexts, such as political districting.

 

Researchers in this field are particularly interested in mathematical and computational tools that can be used to draw U.S. Congressional seat boundaries. Jeanne Clelland, a differential geometer at the University of Colorado, Boulder, has been working on redistricting for several years. But in 2021, she ran into a problem she had never seen before. 

 

Congressional districts are based on smaller units, either census blocks or voting precincts. Clelland was using a precinct map at the time where each precinct is described by a polygon with a population of approximately 2,000 or 3,000 people. The map itself is defined by a shape file, a list of all the vertices of those polygons. “They’re a little bit messy,” Clelland says. The polygon edges can overlap or have gaps that need to be resolved before a program can produce a redistricting map.

 

The software Clelland was using included an algorithm that would take a shape file, find all overlaps and gaps between precincts, and automatically assign each affected area to a precinct. Clelland used this program on the map of Colorado she was working with to produce a repaired shape file. “Just for kicks, I did a spot check,” Clelland says. But when she generated possible redistricting maps using the repaired shape file, she discovered that her map had a disconnected Congressional district. “That’s supposed to be completely impossible,” she says. One of the few absolute requirements for Congressional districts is that they be contiguous, so the program she used to create the map shouldn’t have been able to create a disconnected district.

A portion of a generated map of Colorado voting districts, showing the disconnected district in blue. Credit: Jeanne Clelland.

“I started down a rabbit hole,” Clelland says; she has now spent the past few years working on a new algorithm, smart_repair, to prevent this problem from happening again. The root of the problem was that the earlier algorithm would take the overlap of two polygons, cut out the overlapping area, and assign it to the precinct with which it shared the longest boundary. Likewise, it would assign the entirety of a gap to the precinct with which it shared the longest border. 

 

In the case of the Colorado map she was working with, there was a gap that touched a total of 15 different precincts, creating a situation where the districting algorithm thought that certain precincts were adjacent when they were not. She needed to figure out a robust way to subdivide the gaps and overlaps and assign them to districts. 

 

During the SLMath semester, Clelland was able to complete and publish her smart_repair algorithm. “The semester program was amazing,” Clelland says. It gave her the time to focus on research and brought together experts who could share ideas with her. “When I had a question, I didn’t have to send an email and wait three days. I could just walk down the hall and ask somebody.” 

 

Clelland’s algorithm is already being used by organizations including the Metric Geometry and Gerrymandering Group at Tufts University, a leading research group that uses geometry, topology, and computation to address redistricting and maintains a suite of open source software that can be used to produce maps. “I’m just thrilled that this thing I wrote because I needed it seems like it’s going to be a really useful data processing step,” Clelland says.

Evelyn Lamb