At any level of government, a district means that there is a specific piece of government that is supposed to be responible to you and your needs and to the other people in your district. Districts break down governance into managable pieces. School districts let us manage just the schools 'here' and not the schools 'there'. State Legislature and Congressional districts let you elect one specific representative to go off to that part of the government and that's who is supposed to listen to you when you want something out of that level of government. If you and your neighbors have issues arising from the region where you live, then your representative should be able to do a pretty good job of addressing those issues.
Based on the above goals of a district to represent a region of people with common region-based issues, I'm defining this measure of what a good district is:
Across all districts and all people,
The best district map is the one where people have the lowest average distance to the center of their district.
Of course the definition of a good district is open to debate. It's probably not everything that a good district should be, but I think it's a pretty good basic quantifiable measure. I'm using straight-line distance, some people have suggested travel time would be better. That would be interesting but I don't have the time to program up such a solution or computers big enough to run it. There's also the question of whether the "center of the district" should be the geographic center or a population weighted center. I've tried both and to my eye using the geographic center yields better results.
It's also possible for human drawn districts to actually better represent "communities of interest" and other fuzzy but real sociological features. Unfortunately the trend in recent years has not been to do this so until we clean up our representative democracy to give us better representation I think we should take away the map pen and make redistricting fully automatic and impartial. It is possible that this will sometimes draw awkward lines which cut regions in strange ways. It is certain that there are currently a lot of awkward lines cutting regions in strange ways. I think the kind of solution I'm proposing here will be better on average. Actually a lot better, when you use the definition of a good district to measure the quality of current solutions and compare to solutions I'm proposing.
It might be the right kind of thing to measure, but it would take too long. My current solver takes 3-4 hours to find one solution to the California congressional map, and because every run is different due to some random factors I run the solver solid for a couple weeks to get the few best results out of it. During each run it's calculating millions of distances per second. The large amount of map data and extra computer time to calculate all those travel times would slow the process down horribly. It would then require a room filling supercomputer to get an answer in a reasonable amount of time.
It's possible this would be a good measure of district quality. The best district by this measure would be a circle. This would certainly achieve non-gerrymandering. Depending on how the blocks fall it could potentially have a deceptively long jagged perimiter like a coastline. This might accidentally disqualify an otherwise compact district because of a fluke of the mapmaker's pen. Perhaps I'll leave this as an exercise to another interested party, then we can compare results and debate about who has the better map.
I'm putting this here partially as a reminder to do this because I think it's neat. The idea is to find the convex-hull of a district (imagine snapping a rubber band around it which just runs along the outermost points, bridging over places where the district bends inwards) then measure either the land area ratio or the population covered ratio of the convex-hull region to the district's region. This measure should do a good job of finding if a district improperly skips over some region of importance. On the other hand I can imagine an argument that in some cases a donut district is proper, to represent a city with the inner district and the outlying areas with a different district.
Those will have to be broken in some places to get all the districts to equal population. The US Census measures population in small regions called "blocks". In California there are 533163 of these blocks and they break down as in this image (PNG 200KB). Current districting in every state is based on these blocks provided by the Census. My solutions don't generate smooth edges because I can only pick solutions as fine as these blocks. Census blocks are supposed to break along existing political divisions (counties, zip codes, cities) or roads or natural features.
Automated redistricting can sometimes be broken down into 'results based' and 'procedure based'. What I'm going for is results based, I define a way to measure district goodness, but I don't even guarantee that there is any procedure for finding maps of any particular level of goodness (but I've demonstrated that there are good solution methods). Some people prefer to try to define procedure based redistricting. By some set of steps, each step in itself fair, a fair map would be made. But usually nothing about the procedure guarantees that the resulting map will in any way actually be good. Usually I expect these procedures to actually generate pretty bad maps. If they're so simple, then do it. Then we can compare stats and maps.
It is possible for humans to draw districts which actually better represent "communities of interest" and other fuzzy but real sociological features. Unfortunately the trend in recent years has not been to do this. Until we clean up our representative democracy to give us better representation I think we should take away the map pen and make redistricting fully automatic and impartial. It is possible that this will sometimes draw awkward lines which cut regions in strange ways. It is certain that there are currently a lot of awkward lines cutting regions in strange ways. I think the kind of solution I'm proposing here will be better on average. It actually is a lot better, when you use this definition of a good district to measure the quality of current solutions and compare to solutions I'm proposing.
Possibly. There are currently some districts in some states which are created to guarantee that a Black or Hispanic person gets elected to the US House. This might be considered a "good" kind of gerrymandering. It is a distortion of districting to an end that most people agree with. I don't have an exact count but I'm guessing there are more districts the result of bad gerrymandering than good. There is also a better solution for minority representation. Proportional Representation (PR) is an alternative to districting which does a good job of representing people based on identity groups. I think the best solution is to have a mix of districting and PR. Districting maintains the tradition of having your local representative who is more directly accessible for communication and regional issues. PR better represents the mix of identity groups across a state our country. In the US I would like to see a PR Senate and a districted House. Similarly in a State legislature the more numerous body should be districted and the fewer should be PR. (Ireland has had such a mixed PR/districted system since 1922.) Enacting this for the US Senate would require an amendment to be ratified unanimously by all the States. State legislatures should have a relatively easier time implementing such a governmental reform if desired. With or without such changes I'm going to continue advocating for anti-gerrymandering measures because I think they will make more good changes than bad.
Why should a district be constructed to have a near 50%-50% split of people registered for the two major parties? If it were possible to create all districts that way (and in most states it won't) the end result would be to have something like 50% of the seats for one party and 50% for the other, whether this accurately reflects the population at large or not! I suspect that cries for more "competitive districts" will most often come from the slightly smaller of the two major parties. I don't think representative democracy is served by this kind of goal for redistricting. Again, Proportional Representation should be part of the solution of accurately representing the citizenry. If the problem is undesirable entrenched incumbents, I recommend rankings and ratings ballot methods to allow people to safely vote the bums out without compromising or risking spoiled elections.
Dr. Michael McDonald and Dr. Micah Altman have an automated redistricting and districting analysys tool called BARD (Better Automated ReDistricting).
The Splitline Algorithm tries to make fair maps by making a reasonable line at every step; produces very different maps than I do.
Hands Off Redistricting advocates the general concept of an automatic "Optimal Proximity Redistricting Algorithm".
Daves Redistricting has a program you can run to tinker with district maps if you have microsoft silverlight.
George L Clark has written his own redistricting software and come up with some good, substantially similar and interestingly different solutions based on a perimiter measure.
David Burton is working on redistricting for North Carolina. He has a similar approach but wants districts with equal numbers of voters rather than equal population.
High quality authoritative congressional district maps maps are available from nationalatlas.gov
See also bolson's page on election reform which mostly focuses on using rankings or ratings ballots to improve the outcome of elections.
My implementation is a heuristic based gradient descent solver with simulated annealing jitter. It looks at the boundaries between districts and tries to make things better by flipping one block from district A to district B (and possibly over some number of steps, other blocks from B to C and C to A). It doesn't actually directly optimize the measure of population compactness, but looks at related measures like the ratio of the block's distance to the average edge blocks' distances from each district's center, and the ratio of the populations of the two districts the block might go into. Each district grabs up to one block, then centers are recalculated and the cycle begins again checking all the edge blocks.
Part of the point of all this is to increase openness and participation in government. So, nothing is hidden. The tools and the data are all out there, and hopefully better than reinventing all this stuff again.
The automatic redistricting solver can be had here: Open Source Redistricting (GPLv2). The code isn't pretty or easy, but I have put in a little work recently on commenting and cleanup, so it shouldn't be too bad. Someone interested should definitely be able to take this and start tinkering with alternate solving algorithms in pretty short order.