There was some discussion on my earlier thread about Arnold's propositions about rules for drawing district lines that would eliminate the problem of gerrymandering. Wacky Hermit proposed a rule limiting the ratio between the perimeter and area of a district, and Ben Bateman proposed creating a computer model to optimize over a wider range of constraints.
My own thought is that attempts to group people that "fit" together into a district based on demographics is inherently anti-democratic. I think districts should be based on city and county lines, and I would propose two simple rules for two types of districts.
1. Type A districts can contain multiple cities. Any city in a Type A district must be contained entirely within that one district. More than one city can be in a Type A district, but none of those cities can cross the district line.
2. Type B districts can contain part of only a single city. Any city too large to fit in a Type A district can be broken into multiple Type B districts, but no two cities can share a Type B district.
These two rules would ensure that district lines are drawn that represent the local government structure. State and federal representatives should work with the same lines as local representatives; it'll make everyone more accountable, and reduce confusion and waste.
Update:
And then there's bioregional democracy:
Bioregional democracy (or the Bioregional State) is a set of electoral reforms designed to force the political process in a democracy to better represent concerns about the economy, the body, and environmental concerns (e.g., water quality), toward developmental paths that are locally prioritized and tailored to different areas for their own specific interests of sustainability and durability.
Interesting concept, and the article has some examples of how it's put into practice. I'm not an environmental fanatic by any means, but I like the idea of political structures built with environmental interest geographical boundaries in mind -- that way, people in a given environment can treat it as well or as poorly as they want, with minimal effect on other groups.
Update 2:
Richard Tallent emailed with an algorithm he devised to allow voters to draw district lines (with some pixelization).
There is only one fair method to creating districts: as much as possible, let the voters choose for themselves with whom they want to vote. Create a number of similarly-populated geographic "blocks" using a semi-random computer algorithm that is simply taught to avoid splitting up cites or counties where possible. Let each voter pick up to "X" other blocks along with his own, where "X" is the size of the represented region divided by the average number of people in each block. Require that voters can only choose regions either neighboring their own block or sharing some border with at least two other blocks they have also selected. Aggregate these to determine the wishes of each block, and use these numbers to shape the borders with a deterministic best-fit algorithm.
Interesting and possibly effective, but voters won't trust a system that's too complicated for them to understand -- just remember the recent EU Constitution debacle. Why not just take the next step and untie representation from geography entirely?