Brown CS Blog

Click the link that follows for more Brown CS content about Philip Klein.

"Our justice system can't guarantee fair outcomes," says Professor Philip Klein of Brown University's Department of Computer Science (Brown CS), "but it can guarantee fair processes. Gerrymandering is a political issue more than a technical one, but we're trying to reduce the scope for politicians to engineer their districts unfairly."

He's talking about a paper ("Balanced power diagrams for redistricting"), co-written with Vincent Cohen-Addad of the University of Copenhagen and Neal E. Young of the University of California, Riverside, which was recently posted to www.arXiv.org. With the Supreme Court currently weighing arguments in a landmark case on gerrymandering, the process of manipulating the boundaries of an electoral constituency to favor a particular group, it offers an entirely fair process: a computational method of redistricting with several useful advantages.

Philip explains that he was inspired to tackle the challenge of redistricting while working on clustering problems with Cohen-Addad. This type of problem, put simply, involves grouping a set of objects in such a way that objects in the same group, or cluster, are more similar to each other than to those in other clusters. To give a practical example, researchers could create an algorithm to determine the location of hospitals or police stations to ensure that all citizens of a particular city are within their reach.

More specifically, the work from Klein and his collaborators involves k-means clustering, which attempts to split a data set into a fixed number (k) of clusters that each include a center, the arithmetic mean position of all points in the cluster. It breaks geographical areas (for example, the state of Florida) into polygons whose average number of sides is less than six, while minimizing the sum of squared distances of voters to centers. In doing so, it meets the needs of state laws, which dictate (although definitions vary) that districts be contiguous, compact, and not contorted or oddly shaped.

Though finding the best k-means clustering is believed to be computationally intractable, a compromise solution is called a centroidal Voronoi diagram.  Use of centroidal Voronoi diagrams in redistricting has been proposed by a senior at Whitman College, but this solution was lacking in one key aspect.

"The problem," Philip explains, "is that k-means clustering typically doesn’t consider balance, so they didn't necessarily assign the same number of voters to each district. That's a legal necessity, so we started with the same objectives of contiguousness and compactness, but added the constraint that the populations must be maximally balanced, with each district having at most one more voter than another."

The solution proposed is to use power diagrams, which partition the data set further by moving the centers into a third dimension at varying distances, thus making them less or more accessible. Previous researchers have proposed algorithms for finding balanced power diagrams, especially in graphics, but in that setting the problem scale is much larger, so these algorithms prioritize speed over accuracy.  

The algorithm created by Philip and his collaborators works by starting with a set of centers, performing the novel step of assigning voters to them collectively to exactly minimize the sum of squared distances while preserving balance, then moving the centers and assigning voters again, continuing until further steps of this kind don’t improve the solution. Currently, the algorithm ignores factors like topography and the presence of water, which affect a voter's ability to get to voting stations, but Philip notes that they could be modified to take them into account.

A close look at a proposed redistricting for California reveals that even in areas where many small districts are needed, the districts remain contiguous and compact, with reasonable shapes.

"The code is public, and we’re really hoping to draw attention to this idea," he says, noting that in some states, individual citizens are able to submit redistricting plans for future use. "People have been saying repeatedly that we need a mathematical measure for this problem, and now we have one. It's perfectly possible to redistrict fairly, and I like the fact that our diagrams make that very clear to anyone who might be interested, regardless of whether they're a computer scientist. This work shows people that if we want to redistrict without gerrymandering or political engineering, here's a way."

For more information, click the link the follows to contact Brown CS Communication Outreach Specialist Jesse C. Polhemus.