District-Shortening Flow

using differential geometry to analyze compactness

This project uses interactive widgets and visualizations to explore the use of curve-shortening flow to analyze the geometric shape of electoral districts.
The code to generate the figures is based on Patrick Girardet's implementation of Curve-Shortening Flow and the project includes joint work with Emilia Alvarez, Daryl Deford, Michelle Feng, Patrick, Natalia Hajlasz, Eduardo Chavez Heredia, Lorenzo Najt, Sloan Nietert, Aidan Perreault, and Justin Solomon.

A case for "multiscale compactness"

While the geometric shape of a district is not the measure by which gerrymandering is defined, it often drives the popular narrative around what districts are and are not gerrymandered. A quick Google search for a term like "most gerrymandered districts" will return a litany of articles naming-and-shaming districts like the Illinois-4th, the previous iteration of the North Carolina-12th, and the Maryland-3rd. While all three of these districts were (allegedly) drawn with some electoral intent, most of the press surrounding them is about their contorted shapes rather than their effect on the outcomes of elections.


IL-4

NC-12 (2011-2016)

MD-3

The term used to describe whether a district's shape is aesthetically pleasing or not is compactness and it it a shockingly underspecified concept. Several mathematical definitions have emerged throughout the years, but the most common definitions don't even agree with each other on what a "compact" shape is. Some definitions say that a circle is the most compact shape and some don't. Some say that a compact shape with a ragged boundary is still fairly compact, and some don't. Some measures say that long, thin rectangles are very compact, and some say that they are very noncompact. To make matters worse, this word compactness can be found in legal codes, where some states say that districts must be "(reasonably) compact" but don't give any suggestions for how to measure the compactness of a district.

One of the most popular measures of compactness is called the Polsby-Popper score. One formulation of this is as $ \frac{4\pi \mathrm{Area}}{\mathrm{Perimeter}^2}$, and it has several attractive mathematical properties. It's always a number between zero and one, and it's one exactly when the shape we're looking at is a circle. This score also varies continuously as the boundary of the shape is pulled and stretched. Another nice property is that it is scale-invariant , meaning that blowing up a shape doesn't change it's Polsby-Popper score. This means that it's appropriate to use this score to examine districts of different sizes.

However, this score has some drawbacks which make its use in redistricting applications somewhat questionable. First, it's very sensitive to small changes in the shape's boundary. A circle with a ragged boundary may have the same Polsby-Popper score as a very snaky shape.


PP=.25

PP=.25

This is a problem because many boundaries in political geography, such as city lines as well as coastlines and rivers are natural choices to use as district borders, but they tend to be jagged, which distorts the Polsby-Popper score. This also means that the score is sensitive to the resolution of measurement . As maps become more detailed, things like coastlines look more and more rough, and so the same district's Polsby-Popper score may vary by a factor of as much as three depending on how precise the geographic measurements are. Richard Barnes and Justin Solomon explore this in more detail in their paper, here.

One way to avoid some of these issues is to try to keep more information about the shape of the district in our compactness score. In this way, we can try to disentangle the instability from the boundary effects from the larger-scale geometric features of the shape. The Polsby-Popper score (and others) assign a single number to each district, but we can use some more sophisticated math to develop methods which assign a list of numbers to each district. While we're thinking about more robust measures of compactness, we can write down a few reasonable properties we'd like our measure to satisfy:

We'll use a small twist on a technique from differential geometry called curve-shortening flow to develop a multiscale compactness measure which satisfies these criteria.

Curve-Shortening Flow

What is curve-shortening flow? We'll restrict our attention to simple, closed curves in the plane, which means that it doesn't cross itself or double back, and it forms the boundary of a region. Given such a curve, curve-shortening flow is a process which shrinks the region so that its area decreases at a constant rate and its length (perimeter) decreases as quickly as possible. This process will transform the boundary of any kind of region we might think of to a "round point" (the limit of a circle as you take its radius to zero). We can intuitively think of curve-shortening flow as slowly "ironing out" the boundary of our region, where it eliminates small wrinkles very quickly and takes a little bit longer to adjust large deformities. Our small twist is that we also rescale the region at every step so that the area remains fixed. Therefore, this process will slowly transform any shape into a circle of the same area.

Here's a brief animation of this transformation applied to MD-3, played forwards (district to circle) and backwards (circle to district).

The procedure to perform curve-shortening flow is pretty straightforward. At each point on the boundary of our region, we'll find the tangent line and move that point inward in the direction perpendicular to the tangent. How far to move it will depend on the curvature of the boundary at the point. Intuitively, curvature measures how "curvy" the boundary is at a particular point. If our point lies on a very bendy portion of the boundary, then the curvature at that point is large. If our point is on a portion that looks like a straight line, then the curvature is small.

Formally, we can measure curvature in the following way. First, we can look at the neighborhood of our point on the boundary and imagine that it's a small segment on the circumference of a circle with some radius $r$, called the osculating circle. Then, the curvature at that point is $1/r$ if it's a point of positive curvature or $-1/r$ if it's a point of negative curvature. If we're looking at a point on a line segment, then we say that the curvature is zero. In this small illustration, a step of curve-shortening flow will move the point with the small blue circle outward, since it's a point of negative curvature, and the point with the large yellow circle inward, since it's a point of positive curvature. This is indicated by the directions of the arrows. Since the blue circle is smaller than the yellow circle, the first point will be moved further than the second.

We can make two observations about the behavior of curve-shortening flow on a shape. First, since points on really curvy portions of the boundary are moved further, it should smooth out the boundary very quickly. Second, since indentations in the shape are pushed outward and appendages sticking out get pulled inward, the shape will get progressively "nicer" as we run the process; it should never grow a new appendage or suddenly develop a jagged boundary.

Algorithmics

The next concern is whether we can actually run curve-shortening flow on a real shape, or if it just exists as a theoretical construct. The procedure we described above applies to smooth curves and technically requires we compute the curvature at every one of an infinite number of points, which is no-good if we're concerned with developing something practical. Furthermore, we conveniently ignored how the procedure operates at points on the boundary which are not smooth, such as vertices of a polygon. Since the boundaries of districts are described as polygons in geographic shapefiles, this behavior is more than simply a technicality.

To solve this, we need both a sensible replacement for the tangent line at a point as well as a good way to define curvature for things that aren't, well, curved. Recall from differential calculus that the tangent line at a point is the limit of secant lines through pairs of points, one on each side of our point, as these two points move closer to our point. So, instead of using a tangent line, we can use the line passing through two points very close to our point.

For curvature, we're going to do something similar. Since any three (non-collinear) points define a circle, if we take this pair of points along with our point of interest, we have a circle which touches the boundary of our region in a way that's almost like the osculating circle. In fact, much like we can define the tangent line as coming from a limit of these secant lines, we can also define the osculating circle to be the limit of the circles defined by these three points as the two nearby points approach the point we're looking at. All of this sounds a little complicated, but once we go through this construction, we can convince ourselves of the fact that these substitutions mean that we move each vertex along the line which bisects its angle at a distance proportional to $\pi$ minus the measure of that angle. This makes sense intuitively, since the wider the angle, the less bendy the shape is at that point, so the curvature should be smaller.

Turning Curve-Shortening Flow into a Compactness Measure

We've given an explanation of curve-shortening flow and described how one might be able to implement an algorithm to compute it, we can move on to designing a compactness score which can be derived from it. First, since we're playing around with things that depend on distances, we're going to assume that all of the regions we might want to examine have the same area. In our version of curve-shortening flow, we keep the area of the region fixed and the perimeter decreases monotonically until the region becomes a circle, we might conjecture that regions which are more compact become circles more quickly than non-compact ones. Let's fix our area to be $\frac{1}{4\pi}$, which seems an odd choice, except that it makes the circle we get at the end of the process have circumference equal to one.

Our measure will be the plot of "number of curve-shortening flow steps" against the "perimeter of the figure at each step". We'll take a second to argue that this satisfies all four of our desiderata. This page serves as explanation and in the previous section, we described a method to compute the curve-shortening flow procedure, which covers the first two items. The measure is stable since any small perturbation in a shape will be quickly smoothed out by the curve-shortening flow procedure, meaning that we get almost identical plots for two very similar shapes. The final criterion is that the measure be informative, and we can at the very see that it's at least as informative as the Polsby-Popper score, since we can recover the Polsby-Popper score from the information contained in these plots. Specifically, because we've normalized the area of these shapes very particularly, the Polsby-Popper score of a region is exactly $1/\mathrm{Perimeter}$ after we've run zero steps of curve-shortening flow. We'll see below that we can glean much more information than just the Polsby-Popper score from these plots, but since it's at least as good as a standard measure, we can be satisfied that our plots are not meaningless.

Comparing Plots

To demonstrate this measure, we'll examine the plots of three districts. Below are images of the three districts as well as animations showing the progress of the curve-shortening flow procedure. The plots on the right have the number of steps on the horizontal axis and the perimeter of the figure at that step on the vertical axis. From left to right, these are "worst offenders" MD-3 and TX-35, as well as OK-1. Since these districts all come from different states, we should be careful not to use this data to inform any judgment about whether or not these districts are part of a gerrymander. This exercise is purely geometric.

MD-3 TX-35 OK-1
Normalized Perimeter MD-3 TX-35 OK-1 1 2 3 4 5 – Curve-Shortening Flow Steps →

There are a few things to observe here. First, the plot for OK-1 is below the other two at every point, and it requires far fewer steps of curve-shortening flow to become something (almost) circular. These demonstrate that, with respect to our measure, OK-1 is much more compact than the other two districts.

Second, we can look at the shapes of the three plots. We observed that OK-1's plot drops very quickly as it takes relatively few curve-shortening flow steps to transform it into a circle. It's original form can be described as two joined rectangles with some irregularities at the boundary. MD-3's plot falls at a slower rate, which reflects the fact that the bizarreness of its geometry is not limited to its boundary, as once the curve-shortening flow smooths it out, what we're left with is something that looks like a snakey 'Y'. TX-35's plot falls quickly at the beginning but then slows down, being outpaced by MD-3 . This is because the boundary smoothing reduces a lot of the district's perimeter, but the long, thin strip which stretches to the southwest requires many steps to pull inward.

We'll remark here that although we've set everything up for the mathematical comparison of district shapes under curve-shortening flow to be sensible, it's important to recognize that these comparisons do not, on their own, suggest that any state is or is not gerrymandered, and it is particularly important to recognize that comparisons of compactness across different states are even less meaningful, since different states have different geographic features, population distributions, and legal constraints on the set of allowed districting plans. As a concrete example, it is hard to draw low-perimeter districts in Rhode Island due to its large amount of coastline and small area with dense population, whereas Iowa has much more regular borders, a legal requirement to preserve counties (which also have regular borders), and a fairly sparse population distribution. Rhode Island's districts being less compact than Iowa's with respect to any measure does not suggest that Rhode Island is gerrymandered or that Iowa is not.


Rhode Island

Iowa

To examine a proper comparison of districting plans under the curve-shortening flow compactness measure, we've computed the plots for the districts in three different plans for North Carolina. The first is the plan which was enacted in 2011 and ruled invalid in 2016 as a racial gerrymander, and its flow progressions are represented by the purple dashed plots. During the challenge to this plan, a non-partisan group of retired judges proposed a more "fair" plan which is represented below with the solid teal plots. The last is the plan enacted in 2016 as the replacement for the invalid one, which is currently being challenged in the courts as a partisan gerrymander, and its flow progressions are plotted with dotted orange lines.


2011

Judges

2016
Mouse over a column of districts to highlight the three corresponding plots in the graph. The shaded regions are the average plus/minus one half of the standard deviation of the value of all districts in the plan after a particular number of rounds of curve-shortening flow and the thin plots are the averages.
Normalized Perimeter 1 2 3 4 5 – Curve-Shortening Flow Steps →
2011 Judges 2016 NC-1 NC-2 NC-3 NC-4 NC-5 NC-6 NC-7 NC-8 NC-9 NC-10 NC-11 NC-12 NC-13
The 2011 districts and 2016 districts come from the U.S. Census Bureau's Tigerline files. The shapes for the judges' plan were graciously provided by Jonathan Mattingly and his group at Duke University. The judges' districts were renumbered to best align geographiclaly with the 2016 plan.

In this figure we can see that the 2011 plan as a whole is less compact than the 2016 plan, which is less compact than the judges' plan. We can see that the purple band begins above the orange one, and falls very quickly at the beginning. This suggests that much of the difference in compactness between the 2011 plan and the 2016 plan is attributable to boundary effects rather than the districts being fundamentally more regularly shaped. Additionally, the 2011 districts have more small tendrils which make them less compact at the left end of the scale, but these are ironed out relatively quickly by the curve-shortening flow process.

The judges' plan's band is below the 2011 plan two until we have run the curve-shortening flow for a long time. Thus suggests, that unlike the 2016 plan, the districts in the judges' plan have fundamentally more compact shapes than the 2011 plan, rather than simply having nicer boundaries.

This example highlights a fundamental weakness in using the Polsby-Popper score, or any other single-valued compactness measure. The average Polsby-Popper scores of the districts are represented by the far left ends of the plots. Looking only at these numbers, we'd conclude that the 2016 plan is much more compact than the 2011 plan. However, by using a richer, multiscale compactness measure, we can observe that this is not the case, and we can make the more nuanced observation that the boundaries of the districts in the 2016 plan are nicer than those of the 2011 plan, but the shapes are fairly similar.

Use the widget below to examine up to any three districts in the 115th Congress (those used for the 2016 elections) at a time. The slider below each image and you can use the buttons with arrows move through the curve-shortening flow animations. Can you find districts which appear to be non-compact because of their large perimeters but have plots which drop off very rapidly? Are there districts which the flow process sends to circles even more slowly than it does for TX-35 and MD-3? Are there districts which are less compact under this measure than some of the "worst offenders" from popular media articles?

Use the dropdowns to choose a state and a district to examine. Move the sliders to animate the curve-shortening flow process. The arrow buttons step through this animation one frame at a time, for a finer-grained view.









Normalized Perimeter 1 2 3 4 5 – Curve-Shortening Flow Steps →
Small islands have been removed from many coastal districts, including the Alaskan Aelutians. Hawaii's districts both span several islands, so the shapes presented here are not accurately descriptive of the state's districts. We extracted these shapes from a modified version of the U.S. Census Bureau's Cartographic Boundary File. The Cartographic Boundary File is clipped to the coastline, so the North Carolina districts which border the ocean appear differently here than in the previous figure.

In Conclusion...

We began by articulating a case for using multiscale compactness measures which capture more information than scalar scores can. Our reason for this is the observation that scores like Polsby-Popper are highly sensitive to boundary effects which are prevalent in geographic applications. We introduced the use of curve-shortening flow as an example of a multiscale measure which captures meaningful information about the geometry of a district without being susceptible to the perturbative effects which distort Polsby-Popper scores.

We point out here that we are not proposing these scores or the data presented in this page be used to support or challenge any districting plan, as gerrymandering is not a function solely of the geometry of a districting plan. In particular, an analysis of alleged gerrymandering demands the incorporation of demographic and economic data as well as comparisons to the other possible plans which could have been enacted, since geography and population distributions place significant constraints on which districting plans are and are not feasible. Rather, we hope that this page and the interactives inspire the application of more modern mathematical methods to the redistricting problem as well as challenge the popular narrative that scalar measures of compactness strictly define what is and is not a gerrymander.