However, the only objective consideration in drawing census tracks that I am aware of (in the U.S.) is that they contain 5-10,000 persons, which leaves census tract drawing vulnerable to political manipulation.
I think this number is actually the crux of the issue. If the size of a census tract is far smaller than the size of the district, then I would argue it doesn't matter how much bias there is in how the tracts are defined. I think we can count on at least 10 tracts per district, as a conservative assumption.
In the case of congressional districts, that's a VERY conservative assumption. The average congressional district has over 600,000 people in it. When you have that many census tracts, manipulation of the algorithm is simply impossible.
Consider, further, the nature of a gerrymandered district. Gerrymandering typically produces long, sliver-shaped districts that try to capture a particular constituent. But what to slivers have a lot of? Perimeter length, that's what. That means lots of road connectivity to the surrounding districts, which means it's pretty unlikely that they would be split apart by this algorithm. Which means the gerrymandering tends to produce no effect.
If someone was willing to precisely define the conditions, I could probably code something up.
Well the first step would just be to write the basic algorithm: one that takes a weighted graph and returns the N subgraphs that results in the lowest total severed edge weight. You would also need to assign a population number to each node, and require that the total solution have roughly equal population in each sub-graph.
-Adam
---- Election-methods mailing list - see http://electorama.com/em for list info
