Roland Fryer spoke here last week on this interesting paper.

New York (actual redistricting):

New York (compact districting algorithm):

The idea is to measure the compactness of a districting plan in a state using the average squared distance between voters within districts. This seems like a great idea in that the measure is precisely defined and depends on where people live. I’m not quite sure how compactness would be balanced against other concerns, though. As Fryer notes, U.S. courts have required districts to be drawn with identical populations within states–a discrepancy of just 100 votes is too much–which is a little silly considering that districts change by thousands of votes between redistrictings, which are typically done every 10 years.

Also, it’s not clear that the compactness measure captures all the ideas of compactness one might have. One can actually construct a simple example where the most “natural” (in terms of preserving natural community boundaries) districting is actually the *least* compact possible plan. Consider a South-Dakota-shaped rectangular state that must be divided into 2 districts, where 1/2 the pop lives in city exactly in the center of the state, and the rest of the pop is uniformly distributed through the state. In this case, the most compact districting divides the state with a north-south line down the middle (splitting both the city and the rural area), and among the *least* compact plans is the districting that has the city as one district and all the rest of the state as the other.

The noncompactness of the city/countryside plan can be seen from a mathematical identity, that Fryer’s compactness measure–minimizing the average squared distance within districts–is equivalent to miminizing the variance (more precisely, the trace of the covariance matrix) within districts, and thus maximizing the variance of the centroids between districts. The city/countryside plan (in my simple example) has the centroids of the 2 districts in identical positions, thus minimizes compactness.

This is not to dismiss Fryer’s idea, just to give an example to throw at it to better understand what it’s doing.

Finally, a small technical point: the district numbers seem to have ben assigned by hand (see the New York example above). It wouldn’t be hard to add an automatic numbering feature, numbering the new districts to minimize the average squared distances from the centroid of each new district to that of the same-numbered new district. This would be done after the districts have been drawn, so it would just aid in interpretation and not affect the way that Fryer’s program draws the actual district lines.

Hi Andrew,

It looks like one of the theoretical results in the Fryer paper (the fact that the optimal partitioning is a power diagram) reproves a result from 1994

http://doi.acm.org/10.1145/177424.178042