A Political Redistricting Tool for the Rest of Us - Other Approaches to Redistricting

Here we discuss two possible avenues of extending this work. The first comes from the literature of centroidal Voronoi diagrams. The second from the idea of crowd-sourcing.

Lloyd-type Iterations

The approach of the applet to finding an "optimal" redistricting plan is reminiscent of another algorithm related to Voronoi diagrams–that of the Lloyd algorithm for computing centroidal Voronoi diagrams. [Du] In a Lloyd algorithm, we start with a Voronoi diagram.

A Voronoi diagram for 4 centers (white) and the corresponding centroids (red).

A Voronoi diagram (VD) for a collection of points, called centers, is simply a partition of the set into regions where each point in the region is closer to its center than any other center. In general, the centroids of each region will not coincide with the centers of the regions.

The Lloyd algorithm moves the centers (white) to their corresponding centroids (red) and recomputes the Voronoi diagram and repeats. After many iterations, the centers and the centroids coincide and the result is known as a centroidal Voronoi diagram (CVD). Typically a CVD has a more regular appearance than an arbitrary VD.

A centroidal Voronoi diagram for 4 points (white) and the corresponding centroids (red).
Here they coincide after Lloyd iteration.

An interesting avenue of future exploration would be to develop a Lloyd-type algorithm for the redistricting applet. Rather than have the user manually move the centers to some new positions that may improve the redistricting plan, one could devise a systematic placement scheme that iteratively "improves" the districts. Perhaps, it adjusts to minimize perimeter. Or, more generally, perhaps the scheme adjusts to optimize a weighted list of other desirable characteristics that we have not addressed here.

Crowd-sourced Redistricting

Consistent with the interactivity of our redistricting applet, the authors can envision a scheme where the residents of a state are invited to play a redistricting game. The results of hundreds (or thousands) of players could be aggregated to build a starting point for state redistricting committees. This approach has the advantage of being more participatory and hence confers the democratic credibility that is so necessary to the redistricting process.