This particular problem is a bit too applied for my taste, but it's always nice to see mathematicians in the news:
For decades, math and computer science have played a profound role in the drawing of legislative districts. And it's hard to argue that they've improved the process. As the amount of information and computing power available to the gerrymanderers has ballooned, they have gotten much better at surgically crafting districts to their precise desires.So, with a reapportionment of House seats coming up in just over two years, after the next decennial census, mathematicians are now plotting their revenge. After 2010, most states will redraw their congressional districts to account for population shift, sometimes adding or subtracting seats. It's tough to find many defenders of the status quo, in which a supermajority of House seats are noncompetitive. (Congressional Quarterly ranked 324 of the 435 seats as “safe” for one party or the other in 2008.) The mathematicians--and social scientists and lawyers--who gathered to discuss the subject Thursday are certain there's a better way to do it. They just haven't quite figured out what it is.
And a little math humor is always appreciated:
“The idea is that circles are the best shape for districts,” said George Washington University's Daniel Ullman, talking about one school of thought. “Unfortunately, they don't tessellate well.” This was apparently a joke, because the room burst out laughing. For the rest of the afternoon, the word tessellate never failed to produce giggles.
- Log in to post comments
Sounds like a central Voronoi tessellation is what we need here...
Neat. I'm teaching a class this year in which we'll cover some of the simple, traditional, methods of apportionment. It is nice to some news like this.
It is an interesting problem. I suspect that the most fair solution would be to, while paying attention to existing political boundaries, like county and township lines, minimizing the sums of the moments of inertia of all the districts would probably be most fair and politically neutral.
I'd like to see a rule that for an area to qualify as a district, it must be possible to draw a straight line from any point in the district, to any other point in the district, without that line entering another district. Gerrymandering is just a less direct form of voter suppression.
Are you kidding, Science Avenger? There has never been such a redistricting and there never will be such a redistricting. Even your basic city limits fail this convexity test and just about every county in California does, too. (The little rectangular ones in Texas are probably okay.) More respect for political boundaries like county lines and city limits would be a perfectly reasonable guideline, but your suggestion is flat-out impossible for any kind of real-world districts.
"More respect for political boundaries like county lines and city limits would be a perfectly reasonable guideline, but your suggestion is flat-out impossible for any kind of real-world districts."
Are you kidding, Zeno? We're mathematicians! Since when have we favored practical considerations over the more elegant solution? And convex districts are certainly more elegant.
In all seriousness, you're right that convexity is just not going to happen. In addition to the political-boundary problems, there is also the fact that regions of the same area will NOT have the same population, and we'd like to equalize the district populations as much as possible.
The goals I'd like to see in redistricting is that districts be
(a) continuous
(b) compact (which could be high area/perimeter ratio or low moment of inertia)
(c) of equal population
(d) determined by a nonpartisan method (the inputs to the redistricting should be population distribution, not partisan/racial distribution.
I've tried to think of "flow" algorithms which would take a redistricting which doesn't meet those rules (or at least, rules b and c) and by shifting the borders incrementally to move into a set of balanced districts, but I've not had a lot of luck.
One solution I have heard of for redistricting is recursive subdistricting: Given a district with 2n (2n+1) representatives, divide it by a straight line into two subdistricts with population ratios of n:n (n:n+1) and redistrict the two subdistrict until you are left with subdistricts with one representative apiece. There are variants on that (draw alternating lines NS and EW, always choose the shortest line, etc)
Would an easy solution not be to abolish districts and use proportional representation between states on population count and within states on votes? Might lead to fewer financial favours for the districts, though.
Circles don't tessellate on a plane but we live (roughly) on a sphere. We just need to dive the entire world into exactly 2 electoral districts and it's fine.
My apologies, I was so anxious to get an old idea out there for discussion I left out a crucial component:
I'd like to see a rule that for an area to qualify as a district, it must be possible to draw a straight line from any zone in the district, to any other zone in the district, without that line entering another district. A zone is an area within city/county/state borders. This gets around the obvious problems Zeno pointed out, and at least for Texas when I devised the idea, it was no problem to alter existing districts to comply. But it would be a lot more difficult for politicians to basically cheat via redrawing lines to their liking in those octopus and snake shapes that are so infamous.
The slide show and explanations of some of these "shapes" are funny too! Illnois 4th and Maryland 3rd are pretty wild...
I agree with Pascal's points:
The goals I'd like to see in redistricting is that districts be
(a) continuous
(b) compact (which could be high area/perimeter ratio or low moment of inertia)
(c) of equal population
(d) determined by a nonpartisan method (the inputs to the redistricting should be population distribution, not partisan/racial distribution.
But would try to include some measure of weighting that respects transportation/travel within an area. There may be a natural barrier such as mountains or river that may limit interaction and hence common bonds that we might seek in a district.
I also like proportional representation, as mentioned by Gerdien.
Maybe we could just limit the fractal dimension of the district?
Steve: Voronoi tessellations FTW.
Have a look at Iowa's districts, which are drawn using a predetermined population formula.
It can be done.